天津大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第六章 树和二叉树

第六章树和二叉树 树的概念和基本术语 二叉树 二叉树遍历 二叉树的计数 树与森林 霍夫曼树

第六章 树和二叉树 ▪ 树的概念和基本术语 ▪ 二叉树 ▪ 二叉树遍历 ▪ 二叉树的计数 ▪ 树与森林 ▪ 霍夫曼树

树的概念和基本术语 树的定义 树是由n(n≥0)个结点的有限集合。如 果n=0,称为空树;如果n>0,则 n有且仅有一个特定的称之为根(Ro的结 点,它只有直接后继,但没有直接前驱 当n>1,除根以外的其它结点划分为m (m>0)个互不相交的有限集T1,T2,,Tm 其中每个集合本身又是一棵树,并且称为 根的子树( SubTree)

树的概念和基本术语 树的定义 树是由 n (n  0) 个结点的有限集合。如 果 n = 0，称为空树；如果n > 0，则 ▪ 有且仅有一个特定的称之为根(Root)的结 点，它只有直接后继，但没有直接前驱； ▪ 当n > 1，除根以外的其它结点划分为m (m >0) 个互不相交的有限集 T1 , T2 ,…, Tm， 其中每个集合本身又是一棵树，并且称为 根的子树(SubTree)

例如 A A 只有根结点的树 06G0OO K 有13个结点的树 其中:A是根;其余结点分成三个互不相交的子集, T1={B,E,F,K,L}:T2={C,G}:T3={D,H,,J,M}, T1,T2,T3都是根A的子树,且本身也是一棵树

A C G B D E F K L H M I J 例如 A 只有根结点的树 有13个结点的树 其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树

树的基本术语 A 1层 B 2层 height 0⊙O3层 K(L 4层 结点 结点的度*子女*祖先*树的深度 叶结点*双亲*子孙树的度 分支结点*兄弟*结点层次*森林

树的基本术语 1层 2层 4层 3层 height = 4 A C G B D E F K L H M I J  结点  结点的度  叶结点  分支结点  子女  双亲  兄弟  祖先  子孙  结点层次  树的深度  树的度  森林

二叉树( Binary tree 定义一棵二叉树是结点的一个有限集合, 该集合或者为空,或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 特点每个结点至多只有两棵子树(二叉树中 不存在度大于的结点) 五种形态 R LR

二叉树 (Binary Tree) 定义 五种形态 一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 L R L R 特点 每个结点至多只有两棵子树（二叉树中 不存在度大于2的结点）

性质 性质1在二叉树的第i层上至多有2-1 个结点。(≥1)[证明用归纳法] 证明:当i=1时,只有根结点,21=20=1 假设对所有j,讠论1,命题成立,即第层 上至多有2H1个结点。 由归纳假设第i-1层上至多有22个结点。 由于二叉树的每个结点的度至多为2,故在 第层上的最大结点数为第-层上的最大结 点数的2倍,即2*21-2=21

性质1 在二叉树的第 i 层上至多有 2 i －1 个结点。(i  1) [证明用归纳法] 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，i>j1，命题成立，即第j层 上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2 i －2个结点。 由于二叉树的每个结点的度至多为2，故在 第i层上的最大结点数为第i-1层上的最大结 点数的2倍，即2* 2i －2= 2 i-1。 性质

性质2深度为k的二叉树至多有2k-1 个结点(k≥1) 证明:由性质可见,深度为k的二叉树的 最大结点数为 ∑(第层上的最大结点数) = =∑211=20+21+…+2k=2k1

性质2 深度为 k 的二叉树至多有 2 k-1 个结点(k  1)。 证明：由性质1可见，深度为k的二叉树的 最大结点数为 = − k i i 1 1 2 ＝2 0 + 21 + … + 2 k-1 = 2 k-1 = k i i 1 (第 层上的最大结点数） ＝

性质3对任何一棵二叉树1,如果其叶 结点数为m0,度为2的结点数为n2则n=n2 +1 证明:若度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定 义 n=n0+n1+n2e=2n2+n1= 因此,有2n2+n1=n+n1+n2-1 n2=nn-110=m2+1

性质3 对任何一棵二叉树T, 如果其叶 结点数为 n0 , 度为2的结点数为 n2 ,则n0＝n2 ＋1. 证明：若度为1的结点有 n1 个，总结点个 数为 n，总边数为 e，则根据二叉树的定 义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1

两种特殊形态的二叉树 定义1满二叉树( Full Binary Tree 一棵深度为k且有2k1个结点的二叉树称为 满二叉树。 满二叉树

定义1 满二叉树 (Full Binary Tree) 一棵深度为k且有2 k -1个结点的二叉树称为 满二叉树。 两种特殊形态的二叉树 6 2 1 4 5 7 3 8 9 10 11 12 13 14 15 满二叉树

定义2完全二叉树( Complete Binary Tree) 若设二叉树的高度为h,则共有h层。除第 h层外,其它各层(0~h-1)的结点数都达到 最大个数,第h层从右向左连续缺若干结点, 这就是完全二叉树。 完全二叉树→ 69000 非完全二叉树

2 1 4 5 3 6 7 2 1 4 5 6 3 非完全二叉树 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (0  h-1) 的结点数都达到 最大个数，第 h 层从右向左连续缺若干结点， 这就是完全二叉树。 6 2 1 4 5 7 3 8 9 10 11 12 完全二叉树