西安电子科技大学出版社：《算法与数据结构》课程教学资源（PPT课件讲稿）第六章 树和二叉树

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

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

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

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

例如 A A B 只有根结点的树 80 有13个结点的树 其中:A是根;其余结点分成三个互不相交的子集, T1={B,E,F,K,}:T2={C,G}:T3={D,H,L,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 C 2层 height 00-3层 K(L 4层 结点 结点的度*子女*祖先树的深度 叶结点双亲*子孙*树的度 分支结点*兄弟*结点层次*森林

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

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

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

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

性质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) 证明:由性质1可见,深度为k的二叉树的 最大结点数为 (第读上的最大结点数) =∑21=20+21++2k1=2k-1

性质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对任何一棵二叉树T,如果其叶 结点数为n,度为2的结点数为n2则n=n2 +1 证明:若度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定 义 n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n Ino tn,t n 2 2 0 n+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且有2k-1个结点的二叉树称为 满二叉树。 8)9 满二叉树

定义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层从右向左连续缺若干结点, 这就是完全二叉树。 完全二叉树 非完全二叉树

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 完全二叉树