树和二叉树(一)

教学目标 了解树的概念 掌握二叉树的概念、性质 掌握二叉树的存储结构 2/24

树的定义 有且仅有一个没有前驱的结点，该结点称为根结点； 树是由n个结点组成的有限集合T，当n=0时称为空树，否则满足条件： 有且仅有一个没有前驱的结点，该结点称为根结点； 其余n-1个结点分成m个互不相交的有限集合T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。 1 2 3 4 5 6 7 3/24

基本术语-1 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树个数称为该结点的度数。 度数为零的结点称为终端结点或叶子结点。 度数不为零的结点称为非终端结点或分支结点。 树中各结点度数的最大值称为树的度数。 2 5 1 3 6 7 4 4/24

基本术语-2 结点的子树的根结点称为该结点的孩子结点，该结点称为孩子的双亲结点。 同一个双亲结点的孩子结点称为兄弟结点。 从根结点到某结点所经过分支上的所有结点称该结点的祖先结点；以某结点作为根的子树中的任一结点称为该结点的子孙结点。 2 5 1 3 6 7 4 5/24

基本术语-3 结点的层数从根结点算起，根结点的层数为1，其它结点的层数等于双亲结点的层数加1。 双亲在同一层的结点互为堂兄弟。 树中所有结点的最大层数称为树的深度或高度。 如果将树中结点的各子树看成是从左到右有次序的，则称该树为有序树，否则称该树为无序树。 有序树中最左边的子树的根称为第一 个孩子，最右边的称为最后一个孩子。 2 5 1 3 6 7 4 6/24

基本术语-4 森林是m(m>=0)棵互不相交的树的集合。 树和森林之间的关系 任何一棵非空树是一个二元组 Tree =（root，F），其中：root是根结点，F是m棵树的森林。 root b d a c e f g h j k i n m o l p 7/24

二叉树 二叉树是由n个结点的有限集合，这个集合或者为空，或者由一个根结点和两棵互不相交的、分别称为此根结点的左子树和右子树的二叉树。 二叉树的定义 二叉树是由n个结点的有限集合，这个集合或者为空，或者由一个根结点和两棵互不相交的、分别称为此根结点的左子树和右子树的二叉树。 二叉树的五种基本形态 空树；只有根；右子树空；左右子树均非空；左子树空。 讨论题：如果二叉树中有3个结点，则有几种不同的形态？ 8/24

二叉树的性质-1 性质１ 在二叉树的第 i 层上最多有 2i-1 个结点(i≥1)。 证明：用归纳法证。 ⑴ 当i=1时，只有一个根结点。 ⑵ 假设第k层上最多有2k-1个结点 　∵二叉树中每个结点最多有2个孩子 　∴第k+1层结点的总数最多为2k-1×2=2k=2(k+1)-1个 ⑶ 由⑴⑵可得结论成立。 9/24

二叉树的性质-2 性质２ 深度为k的二叉树最多有2k-1个结点(k≥1)。 证明： 　　由二叉树性质１可知在二叉树的第 i 层上最多有 2i-1 个结 点(i≥1)，因此深度为 k 的二叉树最多结点数为： 10/24

二叉树的性质-3 性质３ 对任何一棵二叉树T，如果其终端结点数为n0，度为２的结点数为n2，则n0=n2+1。 　∵二叉树中结点的度只能为0、1、2 　∴n=n0+n1+n2；……⑴ 又∵二叉树中除根结点外，每个结点均是且仅是二叉树中某分支结点的孩子 　∴n=2*n2+1*n1+1；……⑵ 由⑴和⑵，可得n0=n2+1，结论成立。 11/24

满二叉树 满二叉树：深度为 k 且有 2k-1 个结点的二叉树。 1 2 3 6 7 4 5 12/24

完全二叉树 完全二叉树：若含n个结点的二叉树中各结点位置与同深度的满二叉树中编号从1至n的结点一一对应，则称完全二叉树。 1 2 3 6 7 4 5 思考题：右图中哪些是完全二叉树？哪些是非完全二叉树？完全二叉树与满二叉树之间有什么关系？ 1 2 3 4 7 5 13/24

二叉树的性质-4 性质４ 具有 n 个结点的完全二叉树的深度为 。 证明：设完全二叉树深度为k ∵前k-1层元素个数为2k-1-1 　　　∴(2k-1-1)+1≤n≤(2k-1-1)+2k-1 　　　　2k-1≤n≤2k-1<2k 　　　∴k-1≤log2n<k 　　　　log2n<k≤1+log2n 　　　∵k是整数 　　　∴k= 14/24

二叉树的性质-5 性质５ 若对一棵有n个结点的完全二叉树中结点按层序进行 编号，则对其中任一结点 i 有： ① 若i=1，则结点 i 为二叉树的根，无双亲， 　 若1<i≤n，则其双亲为结点i/2； ② 若2i>n，则结点 i 无左孩子，否则其左孩子为结点 2i ； ③ 若2i+1>n，则结点 i 无右孩子，否则其右孩子为结点 2i+1。 1 2 3 6 4 5 课堂练习：如果n=15, i=7，则其 双亲结点和左右孩子结点的编号 分别是多少？ 15/24

二叉树的顺序存储结构 0号存储单元存放根结点 #define MAXTSIZE 100 C B E D F G H I J J I H G F E D C B A 9 8 7 6 5 4 3 2 1 0号存储单元存放根结点 #define MAXTSIZE 100 Typedef Elemtype SqBiTree[MAXSIZE]; SqBiTree bt; 16/24

顺序存储结构的问题 A C B E D F G (a) 一棵二叉树 A D C E F G B (b) 改造后的完全二叉树 ∧ D E F G 思考题：如果用顺序存储结构对含有10个结点的二叉树进行存储，则最多会浪费多少个存储单元？ 17/24

二叉树的链式存储结构 lchild rchild parent A ∧ B C D E F G typedef struct BiTNode{ 　TElemType data; 　struct BiTNode *lchild; 　struct BiTNode *rchild; } BiTree; lchild data rchild typedef struct BiTNode{ 　TElemType data; struct BiTNode *parent; 　struct BiTNode *lchild; 　struct BiTNode *rchild; } BiTree; lchild data rchild parent 18/24

小结 本讲主要介绍了树的基本概念及其基本操作，二叉树的基本概念及其基本操作，二叉树的五条重要性质以及二叉树的两种存储结构。 19/24

作业与实验 作业 已知一棵度为m的树中有n1个度数为1的结点，n2个度为 2的结点，…，nm个度为m的结点，问该树中有多少个叶子结点？ 在二叉树的顺序存储结构中实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节的存储空间，每个数据域占k个字节的存储空间。试问对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？ 实验 无。 20/24