Microsoft PowerPoint - 06.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 06.ppt"

鲜弼和
6 years ago
Views:

1 第 6 章树和二叉树 6.1 树的基本概念 6.2 二叉树概念和性质 6.3 二叉树存储结构 6.4 二叉树的遍历 6.5 二叉树的基本操作及其实现 6.6 二叉树的构造 6.7 哈夫曼树本章小结

2 6.1 树的基本概念树的定义形式化定义 : 树 :T={D,R} D 是包含 n 个结点的有穷集合 (n 0) 当 n=0 时为空树, 否则关系 R 满足以下条件 : 有且仅有一个结点 d 0 D, 它对于关系 R 来说没有前驱结点, 结点 d 0 称作树的根结点除结点 d 0 外,D 中的每个结点对于关系 R 来说都有且仅有一个前驱结点 D 中每个结点对于关系 R 来说可以有零个或多个后继结点

3 递归定义 : 树是由 n(n 0) 个结点组成的有限集合 ( 记为 T) 如果 n=0, 它是一棵空树, 这是树的特例 ; 如果 n>0, 这 n 个结点中存在 ( 且仅存在 ) 一个结点作为树的根结点, 简称为根结点 (root), 其余结点可分为 m(m>0) 个互不相交的有限集 T 1,T 2,,T m, 其中每一个子集本身又是一棵符合本定义的树, 称为根 root 的子树 root T 1 T 2 T m

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

5 6.1.2 树的表示 (1) 树形表示法这是树的最基本的表示, 使用一棵倒置的树表示树结构, 非常直观和形象下图就是采用这种表示法 A B C D E F G H I J K L M 逻辑结构表示 1

6 (2) 文氏图表示法使用集合以及集合的包含关系描述树结构下图就是树的文氏图表示法 E B F A C G J D I L H K M A B C D E F G H I J K L M 逻辑结构表示 2

7 (3) 凹入表示法使用线段的伸缩描述树结构下图是树的凹入表示法 A B E A C F G B C D D J E F G H I H I J K L M K L M 凹入表示法逻辑结构表示 3

8 (4) 括号表示法将树的根结点写在括号的左边, 除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构下图是树的括号表示法 A(B(E,F),C(G(J)),D(H,I(K,L,M))) 括号表示法 A B C D E F G H I J K L M

9 6.1.3 树的基本术语 1. 结点的度与树的度 : 树中某个结点的子树的个数称为该结点的度树中各结点的度的最大值称为树的度, 通常将度为 m 的树称为 m 次树 A 度为 3 度为 2 B C D E F G H I J K L M 2. 分支结点与叶结点 : 度不为零的结点称为非终端结点, 又叫分支结点度为零的结点称为终端结点或叶结点在分支结点中, 每个结点的分支数就是该结点的度如对于度为 1 的结点, 其分支数为 1, 被称为单分支结点 ; 对于度为 2 的结点, 其分支数为 2, 被称为双分支结点, 其余类推

10 3. 路径与路径长度 : 对于任意两个结点 d i 和 d j, 若树中存在一个结点序列 d i, d i1, d i2,, d in, d j, 使得序列中除 d i 外的任一结点都是其在序列中的前一个结点的后继, 则称该结点序列为由 d i 到 d j 的一条路径, 用路径所通过的结点序列 (d i, d i1, d i2,, d j ) 表示这条路径路径长度等于路径所通过的结点数目减 1( 即路径上分支数目 ) A B C D E F G J H A 到 K 的路径为 A,D,I,K, 其长度为 3 I K L M

11 4. 孩子结点双亲结点和兄弟结点 : 在一棵树中, 每个结点的后继, 被称作该结点的孩子结点 ( 或子女结点 ) 相应地, 该结点被称作孩子结点的双亲结点 ( 或父母结点 ) 具有同一双亲的孩子结点互为兄弟结点进一步推广这些关系, 可以把每个结点的所有子树中的结点称为该结点的子孙结点从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点 A B C D E F G J H I K L M

12 5. 结点的层次和树的高度 : 树中的每个结点都处在一定的层次上结点的层次从树根开始定义, 根结点为第 1 层, 它的孩子结点为第 2 层, 以此类推, 一个结点所在的层次为其双亲结点所在的层次加 1 树中结点的最大层次称为树的高度 ( 或树的深度 ) 6. 有序树和无序树 : 若树中各结点的子树是按照一定的次序从左向右安排的, 且相对次序是不能随意变换的, 则称为有序树, 否则称为无序树 A B C D E F G J H 1 2 I 3 K L M 4

13 7. 森林 :n(n>0) 个互不相交的树的集合称为森林森林的概念与树的概念十分相近, 因为只要把树的根结点删去就成了森林反之, 只要给 n 棵独立的树加上一个结点, 并把这 n 棵树作为该结点的子树, 则森林就变成了树 A B C D E F G J H I K L M

14 6.1.4 树的性质性质 1 树中的结点数等于所有结点的度数之和加 1 证明 : 根据树的定义, 在一棵树中, 除根结点外, 每个结点有且仅有一个前驱结点也就是说, 每个结点与指向它的一个分支一一对应, 所以除根结点之外的结点的个数等于所有结点的分支数 ( 度数 ) 之和, 从而可得树中的结点数等于所有结点的度数之和加 1 A B C D E F G J H 度之和 = 分支数分支数 = 结点数 -1 所以, 结点数 = 度之和 +1 I K L M

15 求解方法归纳求解树的结点个数问题 : 对于度为 m 的树, 在 n n 0 n 1 n 2 n m 中只有两个参数未知时, 一般可求出这两个值例如求 n 和 n 0 的求解过程如下 : n=n 0 +n 1 + +n m 度之和 = n-1 度之和 = n 1 +2n 2 + +mn m 所以有 :n=n 1 +2n 2 + +mn m +1 = n 0 +n 1 + +n m 这样 :n 0 = n 2 + +(m-1)n m +1

16 例 : 一棵度为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,10 个度为 1 的结点, 则树 T 的叶子结点个数是 A.41 B.82 C.113 D.122

17 n 0 = n 2 + 2n 3 +3n 4 +1=1+2*10+3*20+1=82

18 性质 2 度为 m 的树中第 i 层 (i 1) 上至多有 m i-1 个结点证明 ( 采用数学归纳法 ) 对于第一层, 因为树中的第一层上只有一个结点, 即整个树的根结点 ; 而由 i=1 代入 m i-1, 得 m i-1 =m 1-1 =1, 也同样得到只有一个结点, 显然结论成立假设命题对于第 (i-1) 层成立, 即度为 m 的树中第 (i-1) 层上至多有 m i-2 个结点则根据树的度的定义, 度为 m 的树中每个结点至多有 m 个孩子结点, 所以第 i 层上的结点数至多为第 (i-1) 层上结点数的 m 倍, 即至多为 m i-2 m=m i-1 个, 这与命题相同, 故命题成立

19 m h 性质 3 高度为 h 的 m 次树至多有 m 1 个结点证明 : 由树的性质 2 可知, 第 i 层上的结点数最多为 m i-1 (i=1,2,,h), 显然当高度为 h 的 m 次树 ( 即度为 m 的树 ) 上每一层都达到最多结点数时, 整个 m 次树具有最多结点数, 因此有 : 1 整个树的最多结点数 = 每一层最多结点数之和 =m 0 +m 1 +m 2 + +m h-1 = m h m 1 1

20 性质 4 具有 n 个结点的 m 次树的最小高度为 h= log m (n(m-1)+1) 证明 : 设具有 n 个结点的 m 次树的高度为 h, 若在该树中前 h-1 层都是满的, 即每一层的结点数都等于 m i-1 (1 i h-1), 第 h 层 ( 即最后一层 ) 的结点数可能满, 也可能不满则该树具有的最小高度 h 可计算如下 : m=3,h=3, 最多结点情况 m=3,h=3, 最少结点情况

21 m 根据树的性质 3 可得 : h m <n h m 1 m 1 乘 (m-1) 后得 : m h-1 <n(m-1)+1 m h 以 m 为底取对数后得 :h-1<log m (n(m-1)+1) h 即 log m (n(m-1)+1) h<log m (n(m-1)+1)+1 因 h 只能取整数, 所以 h = log m (n(m-1)+1) 结论得证 1 1 1

22 例含 n 个结点的三次树的最小高度是多少? 最大高度是多少? 解 : 设含 n 个结点的 ( 为完全三次树时高度最小 ) 的三次树的最小高度为 h, 则有 : h-2 <n h-1 (3 h-1-1)/2 <n (3 h -1)/2 3 h-1 <2n+1 3 h 即 :h= log 3 (2n+1) 最大高度为 n-2

23 6.1.5 树的基本操作树的操作主要分为三大类 : 第一类, 寻找满足某种特定关系的结点, 如寻找当前结点的双亲结点等 ; 第二类, 插入或删除某个结点, 如在树的当前结点上插入一个新结点或删除当前结点的第 i 个孩子结点等 ; 第三类, 遍历树中每个结点, 这里着重介绍

24 树的遍历树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次有以下三种遍历方法 : 先根遍历 : 若树不空, 则先访问根结点, 然后依次先根遍历各棵子树后根遍历 : 若树不空, 则先依次后根遍历各棵子树, 然后访问根结点层次遍历 : 若树不空, 则自上而下自左至右访问树中每个结点注意 : 先根和后根遍历算法都是递归的

25 A 先根遍历的顶点访问次序 : A B E F C D G H I J K 后根遍历的顶点访问次序 : E F B C I J K H G D A 层次遍历的顶点访问次序 : B C D E F G H A B C D E F G H I J K I J K

26 6.1.6 树的存储结构 B E 1. 双亲存储结构这种存储结构是一种顺序存储结构, 用一组连续空间存储树的所有结点, 同时在每个结点中附设一个伪指针指示其双亲结点的位置 A C F (a) D G A -1 B 0 C 0 D 0 E 2 F 2 G 2 (b) 双亲表示法的类型声明如下 : typedef struct { ElemType data; // 结点的值 int parent; // 指向双亲的位置 } Pnode; typedef struct { Pnode nodes[maxnodes]; int n; // 结点数 } PTree;

27 2. 孩子存储结构这种存储结构为每个结点设计两个域 : 一个数据域, 一个数组域存储指向该结点的所有孩子结点的指针数组的大小按树的度 ( 即树中所有结点的度的最大值 ) 定义 B A C B A C D E F D E F G G 结点类型声明如下 : typedef struct node { ElemType data; // 结点的值 struct node *sons[maxsons]; // 指向孩子结点 } SNode, *STree; 其中,MaxSons 为孩子结点个数的最大值

28 3. 孩子兄弟链表存储结构孩子兄弟链表存储结构为每个结点设计三个域 : 一个数据域, 一个指针域指向该结点的第一个孩子结点, 和一个指针域指向该结点的下一个兄弟结点结点的类型声明如下 : A A B C B C D E F D E F G G typedef struct node { ElemType data; // 结点的值 struct node *firstchild; // 指向第一个孩子 struct node *nextsibling; // 指向下一个兄弟 } SBNode, *SBTree ;

29 求树的深度的算法 : int TreeDepth(SBTree T) { if (!T) return 0; else { h1 = TreeDepth(T->firstchild ); h2 = TreeDepth(T->nextsibling); return(max(h1+1, h2)); } } // TreeDepth

30 森林的遍历森林由三部分构成 : 1. 森林中第一棵树的根结点 ; 2. 森林中第一棵树的子树森林 ; 3. 森林中其它树构成的森林 B C D E F G H I J K

31 森林的遍历 1. 先序遍历若森林不空, 则访问森林中第一棵树的根结点 ; 先序遍历森林中第一棵树的子树森林 ; 先序遍历森林中 ( 除第一棵树之外 ) 其余树构成的森林即 : 依次从左至右对森林中的每一棵树进行先根遍历 2. 中序遍历若森林不空, 则中序遍历森林中第一棵树的子树森林 ; 访问森林中第一棵树的根结点 ; 中序遍历森林中 ( 除第一棵树之外 ) 其余树构成的森林即 : 依次从左至右对森林中的每一棵树进行后根遍历

32 树和森林的遍历树没有中根遍历 : 因为一棵非空树的根结点可能有 2 个以上子树, 无法确定根结点的遍历次序森林的中序 : 可以看作是 : 森林根森林森林没有后序遍历 : 若子树森林森林根, 则把同一棵树割裂

33 6.2 二叉树概念和性质二叉树概念二叉树是有限的结点集合这个集合或者是空或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成注意 : 二叉树的定义是一种递归定义

34 二叉树的五种基本形态 : 空树只含根结点 N 右子树为空树左子树为空树左右子树均不为空树 N N N L R L R

35 在一棵二叉树中, 如果所有分支结点都有左孩子结点和右孩子结点, 并且叶结点都集中在二叉树的最下一层, 这样的二叉树称为满二叉树下图所示就是一棵满二叉树可以对满二叉树的结点进行连续编号, 约定编号从树根为 1 开始, 按照层数从小到大同一层从左到右的次序进行图中每个结点外边的数字为该结点的编号 1 A 2 3 B C D E F G H I J K L M N O 满二叉树

36 若二叉树中只有最下面两层的结点的度数可以小于 2, 并且最下面一层的叶结点都依次排列在该层最左边的位置上, 则这样的二叉树称为完全二叉树如下图所示为一棵完全二叉树同样可以对完全二叉树中每个结点进行连续编号, 编号的方法同满二叉树相同图中每个结点外边的数字为对该结点的编号 1 A 2 3 B C D E F G H I J K 完全二叉树

37 6.2.2 二叉树性质性质 1 非空二叉树上叶结点数等于双分支结点数加 1 证明 : 设二叉树上叶结点数为 n 0, 单分支结点数为 n 1, 双分支结点数为 n 2, 则总结点数 n=n 0 +n 1 +n 2 在一棵二叉树中, 所有结点的分支数 ( 即度数 ) 之和应等于单分支结点数加上双分支结点数的 2 倍, 即总的分支数 =n 1 +2n 2 由于二叉树中除根结点以外, 每个结点都有唯一的一个分支指向它, 因此二叉树中有 : 总的分支数 = 总结点数 -1 由上述三个等式可得 :n 1 +2n 2 =n 0 +n 1 +n 2-1 即 :n 0 =n 2 +1

38 性质 2 非空二叉树上第 i 层 (i 1) 上至多有 2 i-1 个结点由树的性质 2 可推出性质 3 高度为 h(h 1) 的二叉树至多有 2 h -1 个结点由树的性质 3 可推出性质 4 具有 n 个 (n > 0) 结点的完全二叉树的高度为 h= log 2 n+1 或 h= log 2 n +1 由完全二叉树的定义和树的性质 3 可推出

39 性质 5 对完全二叉树中编号为 i 的结点 (1 i n, n 1, n 为结点数 ) 有 : (1) 若 i n/2, 即 2i n, 则编号为 i 的结点为分支结点, 否则为叶子结点 (2) 若 n 为奇数, 则每个分支结点都既有左孩子结点, 也有右孩子结点 ; 若 n 为偶数, 则编号最大的分支结点只有左孩子结点, 没有右孩子结点, 其余分支结点都有左右孩子结点 (3) 若编号为 i 的结点有左孩子结点, 则左孩子结点的编号为 2i; 若编号为 i 的结点有右孩子结点, 则右孩子结点的编号为 (2i+1) (4) 除树根结点外, 若一个结点的编号为 i, 则它的双亲结点的编号为 parent= i/2 也就是说, 当 i 为偶数时, 其双亲结点的编号为 i/2, 它是双亲结点的左孩子结点 ; 当 i 为奇数时, 其双亲结点的编号为 (i-1)/2, 它是双亲结点的右孩子结点

40 例 : 已知一棵完全二叉树的第 6 层 ( 设根为第 1 层 ) 有 8 个叶结点, 则该完全二叉树的结点个数最多是 A.39 B.52 C.111 D.119 例 : 一棵满二叉树中共有 n 个结点, 其中有 m 个叶子结点, 高度为 h, 则 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -1

41 第六层有 32 个节点, 其中有 8 个是叶结点, 作为完全二叉树它最多有七层第六层的其余 24 个结点在第七层最多有 48 个子节点, 也就是第七层的节点有 48 个所以前六层的 63 加第七层的 48 就是 111 个节点 n=2 h -1

42 6.3 二叉树存储结构二叉树的顺序存储结构二叉树的顺序存储结构中结点的存放次序是 : 对该树中每个结点进行编号, 其编号从小到大的顺序就是结点存放在连续存储单元的先后次序若把二叉树存储到一维数组中, 则该编号就是下标值加 1( 注意 C/C++ 语言中数组的起始下标为 0) 树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同利用二叉树的性质 4

43 1 A 2 3 B C D E F G H I J K 完全二叉树 A B C D E F G H I J K 顺序存储结构 ( 不用下标为 0 的元素 )

44 2 B 5 1 C A 3 D 14 F 7 E 一般的二叉树先用空结点补全成为完全二叉树, 然后对结点编号 A B D # C # E # # # # # # F SqBTree bt="#abd#c#e######f"; typedef ElemType SqBTree[MaxSize];

45 6.3.2 二叉树的链式存储结构 1. 二叉链表每个结点包含一个数据域 data 和两个指针域 lchild 和 rchild, 分别指向左孩子结点和右孩子结点 ( 即左右子树的根结点 ) 结点结构 : A lchild data rchild typedef struct node B { ElemType data; struct node*lchild,*rchild; } BTNode; C D F E

46 2. 三叉链表与二叉链表相比每个结点增加一个指针域 parent 指向双亲结点结点结构 : parent lchild data rchild A typedef struct node { B ElemType data; struct node *lchild,*rchild; struct node *parent; } BTNode; C D F E

47 森林和二叉树的对应关系设森林 F = ( T 1, T 2,, T n ); T 1 = (root,t 11, t 12,, t 1m ); 二叉树 B =( LBT, Node(root), RBT );

48 由森林转换成二叉树的转换规则为 : 若 F = Φ, 则 B = Φ; 否则, 由 ROOT( T 1 ) 对应得到 Node(root); 由 (t 11, t 12,, t 1m ) 对应得到 LBT; 由 (T 2, T 3,, T n ) 对应得到 RBT 由二叉树转换为森林的转换规则为 : 若 B = Φ, 则 F = Φ; 否则, 由 Node(root) 对应得到 ROOT( T 1 ); 由 LBT 对应得到 ( t 11, t 12,,t 1m ); 由 RBT 对应得到 (T 2, T 3,, T n )

49 树与二叉树转换 : 和树对应的二叉树, 其左右子树的概念已改变为左是孩子, 右是兄弟树 A B C E 存储对应 A ^ ^ B 存储二叉树 A B C D C D E A ^ 解释 ^ D ^ ^ E ^ 解释 A ^ ^ B C ^ D ^ ^ E ^ ^ B ^ D ^ C ^ E ^

50 将树转换成二叉树加线 : 在相邻兄弟之间加一连线删线 : 删除每个结点与其除了左孩子外的其余孩子之间的连线旋转 : 以树的根结点为轴心, 将整棵树顺时针旋转 45 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B A B C D E F E F G H I 树转换成的二叉树其右子树一定为空 G C H D I

51 加线 : 若 p 结点是其双亲结点的左孩子, 则将沿右分支搜索到的 p 的所有右孩子都与 p 的双亲用线连起来删线 : 删除原二叉树中双亲与右孩子之间的连线调整 : 将结点按层次排列, 形成树结构 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 将二叉树转换成树 p p

52 将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根, 再以根结点为轴心, 顺时针旋转 45, 构成二叉树型结构 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 由森林转换成二叉树

53 删线 : 将二叉树中根结点与其右孩子连线, 及沿右分支搜索到的所有右孩子间连线全部删除, 使之变成孤立的二叉树还原 : 将孤立的二叉树还原成树 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 由二叉树转换为森林

54 树森林和二叉树的遍历的对应关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历

55 例设森林 F 中有 3 棵树, 第一第二和第三棵树的结点个数分别为 9 8 和 7, 则与森林 F 对应的二叉树根结点的右子树上的结点个数是 A. 16 B. 15 C. 7 D. 17 例设一棵二叉树是由森林转换而来的, 若森林中有 n 个非终端结点, 则二叉树中无右孩子的结点个数为 A. n-1 B. n C. n+1 D. n+2

56 8+7=15 在二叉树的二叉链表存储结构中, 每个结点的两个指针域 lchild 和 rchild 分别指向左孩子结点和右孩子结点设森林中所有树的叶子结点总数有 m 个, 则总结点数为 m+n 森林转化成二叉树以后, 非终端结点的 lchild 非空空的 rchild 域个数 + 非空的 rchild 域个数 = 总的 rchild 域个数 = m + n; 非空的 rchild 域个数 + 非空的 lchild 域个数 = 总的非空指针域个数 = m + n - 1 而原来森林中有 n 个非终端结点, 所以非空的 lchild 域个数为 n, 代入上面的第二式子得非空的 rchild 域个数为 m-1, 再代入第一式, 得空的 rchild 域个数为 n+1

57 6.4 二叉树的遍历二叉树遍历的概念二叉树的遍历是指按照一定次序访问树中所有结点, 并且每个结点仅被访问一次的过程它是二叉树的基本操作先序遍历二叉树 : 访问根结点 ; 先序遍历左子树 ; 先序遍历右子树中序遍历二叉树 : 中序遍历左子树 ; 访问根结点 ; 中序遍历右子树后序遍历二叉树 : 后序遍历左子树 ; 后序遍历右子树 ; 访问根结点

58 6.4.2 二叉树遍历递归算法由二叉树的三种遍历过程直接得到如下三种递归算法先序遍历的递归算法 : void PreOrder(BTNode *b) { if (b!=null) { printf("%c ",b->data); // 访问根结点 b PreOrder(b->lchild); PreOrder(b->rchild); } } b->lchild b->rchild

59 中序遍历的递归算法 : void InOrder(BTNode *b) { if (b!=null) { InOrder(b->lchild); printf("%c ",b->data); // 访问根结点 InOrder(b->rchild); } }

60 后序遍历递归算法 : void PostOrder(BTNode *b) { if (b!=null) { PostOrder(b->lchild); PostOrder(b->rchild); printf("%c ",b->data); // 访问根结点 } }

61 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法, 计算一棵给定二叉树的所有结点个数解 : 计算一棵二叉树 b 中所有结点个数的递归模型 f(b) 如下 : f(b)=0 若 b=null f(b)=f(b->lchild)+f(b->rchild)+1 其他情况对应的递归算法如下 : int Nodes(BTNode *b) { if (b==null) return 0; else return Nodes(b->lchild)+Nodes(b->rchild)+1; }

62 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法, 计算一棵给定二叉树的高度解 : 计算一棵二叉树 b 高度的递归模型 f(b) 如下 : f(b)=0 若 b=null f(b)=max{ f(b->lchild), f(b->rchild) } +1 其他情况 int Height(BTNode *b) { int num1,num2; if (b==null) return 0; else { num1=height(b->lchild); num2=height(b->rchild); return ( (num1>num2)?num1:num2 ) + 1; } }

63 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法, 计算一棵给定二叉树的所有叶子结点个数解 : 计算一棵二叉树 b 中所有叶子结点个数的递归模型 f(b) 如下 : f(b)=0 若 b=null f(b)=1 若 *b 为叶子结点 f(b)=f(b->lchild)+f(b->rchild) 其他情况 int LeafNodes(BTNode *b) { if (b==null) return 0; else if (b->lchild==null && b->rchild==null) return 1; else return LeafNodes(b->lchild) + LeafNodes(b->rchild); }

64 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法, 计算一棵给定二叉树的所有单分支结点个数解 : 计算二叉树 b 中所有单分支结点个数的递归模型 f(b) 如下 : f(b)=0 若 b=null f(b)=f(b->lchild)+f(b->rchild)+1 若 *b 为单分支结点 f(b)=f(b->lchild)+f(b->rchild) 其他情况 int SSonNodes(BTNode *b) { if (b==null) return 0; else if (b->lchild!=null && b->rchild==null b->lchild==null && b->rchild!=null) return SSonNodes(b->lchild) + SSonNodes(b->rchild) + 1; else return SSonNodes(b->lchild) + SSonNodes(b->rchild); }

65 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法, 计算一棵给定二叉树中值为 k 的结点个数解 : 计算一棵二叉树 b 中值为 k 的结点个数的递归模型 f(b,k) 如下 : f(b,k) = 0 当 b=null f(b,k) = f(b->lchild,k)+f(b->rchild,k)+1 当 b->data=k f(b,k) = f(b->lchild,k)+f(b->rchild,k) 其他情况 int Countk(BTNode *b, ElemType k) { if (b==null) return 0; else if (b->data==k) return Countk(b->lchild,k) + Countk(b->rchild,k) + 1; else return Countk(b->lchild,k) + Countk(b->rchild,k); }

66 例假设二叉树采用二叉链表存储结构, 设计一个算法把二叉树 b 复制到二叉树 t 中解 : 其递归模型如下 : f(b,t) t=null 若 b=null f(b,t) 复制根结点 *b 产生 *t 结点 ; 其他情况 f(b->lchild, t->lchild); f(b->rchild, t->rchild); void Copy(BTNode *b,btnode *&t) { if (b==null) t=null; else { t=(btnode *)malloc(sizeof(btnode)); t->data = b->data; // 复制一个根结点 *t Copy(b->lchild, t->lchild); // 递归复制左子树 Copy(b->rchild, t->rchild); // 递归复制右子树 } }

67 例设二叉树采用二叉链表存储结构, 设计一个算法把二叉树 b 的左右子树进行交换要求不破坏原二叉树解 : 本题要求不破坏原有二叉树, 实际上就是建立一个新的二叉树 t, 它交换了二叉树 b 的左右子树其递归模型如下 : f(b,t) t=null 若 b=null f(b,t) 复制根结点 *b 产生 *t 结点 ; 其他情况 f(b->lchild, t->rchild); f(b->rchild, t->lchild); void Swap(BTNode *b, BTNode *&t) { if (b==null) t=null; else { t=(btnode *)malloc(sizeof(btnode)); t->data=b->data; // 复制一个根结点 *t Swap(b->lchild, t->rchild); // 递归交换左子树 Swap(b->rchild, t->lchild); // 递归交换右子树 } }

68 例假设二叉树采用二叉链表存储结构存储, 试设计一个算法输出一棵给定二叉树的所有叶子结点解 : 输出一棵二叉树的所有叶子结点的递归模型 f() 如下 : f(b): 不做任何事件若 b=null f(b): 输出 *b 结点的 data 域若 *b 为叶子结点 f(b):f(b->lchild); f(b->rchild) 其他情况 void DispLeaf(BTNode *b) { if (b!=null) { if (b->lchild==null && b->rchild==null) printf("%c ",b->data); else { DispLeaf(b->lchild); DispLeaf(b->rchild); } } }

69 例假设二叉树采用二叉链表存储结构, 设计一个算法 Level() 求二叉树中值为 x 的结点的层数解 : 设 Level(b,x,h) 返回二叉链表 b 中值为 x 的结点的层数, 其中 h 表示 b 所指结点的层数若未找到值为 x 的结点, 则 h 为 0 调用 Level(b,x,1) 返回值为 x 的结点的层数 int Level(BTNode *b, ElemType x, int h) { int l; if (b==null) return 0; // 空树时返回 0 else if (b->data==x) return h; // 找到结点时 else { l=level(b->lchild, x, h+1); // 在左子树中查找 if (l==0) // 左子树中未找到时在右子树中查找 return Level(b->rchild, x, h+1); else return l; } }

70 例假设二叉树采用二叉链表存储结构设计一个算法判断两棵二叉树是否相似, 所谓二叉树 t1 和 t2 是相似的指的是 t1 和 t2 都是空的二叉树 ; 或者 t1 和 t2 的根结点是相似的, 以及 t1 的左子树和 t2 的左子树是相似的且 t1 的右子树与 t2 的右子树是相似的解 : 判断两棵二叉树是否相似的递归模型 f() 如下 : f(t1,t2) = true 若 t1=t2=null f(t1,t2) = false 若 t1 t2 之一为 NULL, 另一不为 NULL f(t1,t2) = f(t1->lchild,t2->lchild) && f(t1->rchild,t2-rchild) 其他情况

71 int Like(BTNode *b1, BTNode *b2) //t1 和 t2 两棵二叉树相似时返回 1, 否则返回 0 { int like1,like2; if (b1==null && b2==null) return 1; else if (b1==null b2==null) return 0; else { like1=like(b1->lchild,b2->lchild); like2=like(b1->rchild,b2->rchild); return (like1 && like2); } }

72 6.4.3 层次遍历算法在进行层次遍历时, 对某一层的结点访问完后, 再按照它们的访问次序对各个结点的左右孩子顺序访问, 这样一层一层进行先访问的结点其左右孩子也要先访问, 这与队列的操作原则比较吻合因此层次遍历算法采用一个环形队列来实现层次遍历过程是 : 先将根结点进队, 在队不空时循环 : 从队列中出列一个结点 *p, 访问它 ; 若它有左孩子结点, 将左孩子结点进队 ; 若它有右孩子结点, 将右孩子结点进队如此操作直到队空为止 1 A 2 3 B C D E F G H I J K

73 void LevelOrder(BTNode *b) { BTNode *p; BTNode *qu[maxsize]; // 定义环形队列, 存放结点指针 int front,rear; // 定义队头和队尾指针 front=rear=-1; // 置队列为空队列 rear++; qu[rear]=b; // 根结点指针进入队列 while (front!=rear) // 队列不为空

74 } { } front=(front+1)%maxsize; p=qu[front]; // 队头出队列 printf("%c ",p->data); // 访问结点 if (p->lchild!=null) // 有左孩子时将其进队 { rear=(rear+1)%maxsize; qu[rear]=p->lchild; } if (p->rchild!=null) // 有右孩子时将其进队 { rear=(rear+1)%maxsize; qu[rear]=p->rchild; }

75 输出二叉树中所有从根到叶子的路径例如 : 对左图所示的树, 其输出结果应为 : 1 A 2 3 B C D E F G H I J K A B D H A B D I A B E J A B E K A C F A C G

76 输出二叉树中所有从根到叶子的路径的算法 : void AllPath(BTNode *T, SqStack& S) { // 先序遍历, 用一个栈保存从根到当前结点的路径 SElemType e; if (T!=NULL) { Push(S, T->data ); if (T->lchild == NULL && T->rchild==NULL) PrintStack(S); // 遇到叶子结点输出路径 else { AllPath(T->lchild, S); AllPath(T->rchild, S); } Pop(S, e); // 以该结点为根的路径求完, 退出 } }

77 6.5 二叉树的基本操作及其实现二叉树的基本操作概述 (1) 创建二叉树 CreateBTNode(b, str): 根据二叉树括号表示法的字符串 *str 生成对应的链式存储结构 (2) 查找结点 FindNode(b, x): 在二叉树 b 中寻找 data 域值为 x 的结点, 并返回指向该结点的指针 (3) 找孩子结点 LchildNode(p) 和 RchildNode(p): 分别求二叉树中结点 *p 的左孩子结点和右孩子结点 (4) 输出二叉树 DispBTNode(b): 以括号表示法输出一棵二叉树

78 6.5.2 二叉树的基本运算算法实现 (1) 创建二叉树 CreateBTNode(b, str) DEMO 算法中使用一个栈 St 保存双亲结点用 ch 扫描采用括号表示法表示二叉树的字符串分以下几种情况 : 1 若 ch='(': 则将前面刚创建的结点作为双亲结点进栈, 并置 k=1, 表示其后创建的结点将作为这个结点的左孩子结点 ; 2 若 ch=')': 表示栈中结点的左右孩子结点处理完毕, 退栈 ; 3 若 ch=, : 表示其后创建的结点为右孩子结点, 置 k=2; 4 其他情况 : 当 k=1 时, 表示这个结点作为栈中结点的左孩子结点 ; 当 k=2 时, 表示这个结点作为栈中结点的右孩子结点如此循环直到 str 处理完毕

79 void CreateBTNode(BTNode * &b, char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=null; // 建立的二叉树初始时为空 ch=str[j]; while (ch!='\0') //str 未扫描完时循环 { switch(ch) { case '(': top++;st[top]=p;k=1; break; case ')': top--;break; case ',': k=2; break;

80 } default: p=(btnode *)malloc(sizeof(btnode)); p->data=ch; p->lchild=p->rchild=null; if (b==null) //p 为二叉树的根结点 b=p; else // 已建立二叉树根结点 { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }

81 (2) 查找结点 FindNode(b,x) 采用先序遍历递归算法查找值为 x 的结点找到后返回其指针, 否则返回 NULL 算法如下 : BTNode *FindNode(BTNode *b, ElemType x) { BTNode *p; if (b==null) return NULL; else if (b->data==x) return b; else { p=findnode(b->lchild,x); if (p!=null) return p; else return FindNode(b->rchild,x); } }

82 (3) 找孩子结点 LchildNode(p) 和 RchildNode(p) 直接返回 *p 结点的左孩子结点或右孩子结点的指针 BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; }

83 (4) 输出二叉树 DispBTNode(b) 用括弧表示法输出二叉树对于非空二叉树 b, 先输出其元素值, 当存在左孩子结点或右孩子结点时, 输出一个 ( 符号, 然后递归处理左子树, 输出一个, 符号, 递归处理右子树, 最后输出一个 ) 符号 void DispBTNode(BTNode *b) { if (b!=null) { printf("%c",b->data); if (b->lchild!=null b->rchild!=null) { printf("("); DispBTNode(b->lchild); // 递归处理左子树 if (b->rchild!=null) printf(","); DispBTNode(b->rchild); // 递归处理右子树 printf(")"); } } }

84 6.6 二叉树的构造同一棵二叉树具有唯一先序序列中序序列和后序序列但不同的二叉树可能具有相同的先序序列中序序列和后序序列给定先序中序和后序遍历序列可以唯一确定这棵二叉树的树形仅由一个先序序列 ( 或中序序列后序序列 ), 无法确定这棵二叉树的树形思考 : 给定先序中序和后序遍历序列中任意两个, 是否可以唯一确定这棵二叉树的树形?

85 命题成立否? 同时给定一棵二叉树的先序序列和中序序列就能唯一确定这棵二叉树同时给定一棵二叉树的中序序列和后序序列就能唯一确定这棵二叉树同时给定一棵二叉树的先序序列和后序序列就能唯一确定这棵二叉树

86 定理 6.1: 任何 n(n 0) 个不同结点的二叉树, 都可由它的中序序列和先序序列唯一地确定采用数学归纳法证明当 n=0 时, 二叉树为空, 结论正确假设结点数小于 n 的任何二叉树, 都可以由其先序序列和中序序列唯一地确定已知某棵二叉树具有 n(n>0) 个不同结点, 其先序序列是 a 0 a 1 a n-1 ; 中序序列是 b 0 b 1 b k-1 b k b k+1 b n-1 因为在先序遍历过程中, 访问根结点后, 紧跟着遍历左子树, 最后再遍历右子树所以 a 0 必定是二叉树的根结点, 而且 a 0 必然在中序序列中出现也就是说, 在中序序列中必有某个 b k (0 k n-1) 就是根结点 a 0

87 由于 b k 是根结点, 而在中序遍历过程中先遍历左子树再访问根结点, 最后再遍历右子树所以在中序序列中, b 0 b 1 b k-1 必是根结点 b k ( 也就是 a 0 ) 的左子树的中序序列, 即 b k 的左子树有 k 个结点 ( 注意 k=0 表示结点 b k 没有左子树 ) 而 b k+1 b n-1 必是根结点 b k ( 也就是 a 0 ) 右子树的中序序列, 即 b k 的右子树有 n-k-1 个结点 ( 注意 k=n-1 表示结点 b k 没有右子树 ) 另外, 在先序序列中, 紧跟在根结点 a 0 之后的 k 个结点 a 1 a k 就是左子树的先序序列, a k+1 a n-1 这 n-k-1 个结点就是右子树的先序序列

88 根结点通过 a 0 在中序序列中找到 b k 根结点先序序列 : a 0 a 1 a k a k+1 a n-1 中序序列 : b 0 b 1 b k-1 b k b k+1 b n-1 左子树先序序列, 有 k 个结点右子树先序序列, 有 n-k-1 个结点左子树中序序列, 有 k 个结点右子树中序序列, 有 n-k-1 个结点根据归纳假设, 由于子先序序列 a 1 a k 和子中序序列 b 0 b 1 b k-1 可以唯一地确定根结点 a 0 的左子树, 而子先序序列 a k+1 a n-1 和子中序序列 b k+1 b n-1 可以唯一地确定根结点 a 0 的右子树综上所述, 这棵二叉树的根结点己经确定, 而且其左右子树也都唯一地确定了, 所以整个二叉树也就唯一地确定了

89 例如, 已知先序序列为 ABDGCEF, 中序序列为 DGBAECF, 则构造二叉树的过程如下所示根结点 :A 左先序 :BDG 左中序 :DGB 右先序 :CEF 右中序 :ECF 根结点 :B 左先序 :DG 左中序 :DG 右先序 : 空右中序 : 空根结点 :C 左先序 :E 左中序 :E 右先序 :F 右中序 :F 根结点 :D 左先序 : 空左中序 : 空右先序 :G 右中序 :G 根结点 :E 左先序 : 空左中序 : 空右先序 : 空右中序 : 空根结点 :F 左先序 : 空左中序 : 空右先序 : 空右中序 : 空根结点 :G 左先序 : 空左中序 : 空右先序 : 空右中序 : 空

90 定理 6.2: 任何 n(n>0) 个不同结点的二叉树, 都可由它的中序序列和后序序列唯一地确定同样采用数学归纳法证明实际上, 对于根结点 a k 的左右子树, 在确定左右子树的子中序序列后, 不需要确定左右子树的整个子后序序列, 只需确定子中序序列中全部字符在后序序列中最右边的那个字符即可, 因为这个字符就是子树的根结点根结点通过 a n-1 在中序序列中找到 b k 根结点后序序列 : a 0 a 1 a k-1 a k a n-2 a n-1 中序序列 : b 0 b 1 b k-1 b k b k+1 b n-1 左子树后序序列, 有 k 个结点右子树后序序列, 有 n-k-1 个结点左子树中序序列, 有 k 个结点右子树中序序列, 有 n-k-1 个结点

91 例如, 已知中序序列为 DGBAECF, 后序序列为 GDBEFCA 对应的构造二叉树的过程如下所示根结点 :A 左中序 :DGB 左根 :B 右中序 :ECF 右根 :C 根结点 :B 左中序 :DG 左根 :D 右中序 : 空右根 : 空根结点 :C 左中序 :E 左根 :E 右中序 :F 右根 :F 根结点 :D 左中序 : 空左根 : 空右中序 :G 右根 :G 根结点 :E 左中序 : 空左根 : 空右中序 : 空右根 : 空根结点 :F 左中序 : 空左根 : 空右中序 : 空右根 : 空根结点 :G 左中序 : 空左根 : 空右中序 : 空右根 : 空

92 二叉树表达式 :(a+b*(c-d)-e/f) 其先序序列为 : -+a*b-cd/ef 其中序序列为 : a+b*c-d-e/f 其后序序列为 : abcd-*+ef/- a + * - e / f b - c d

93 二叉树计数问题具有 n 个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂度分析中是很有用的设 B n 是含有 n 个结点的不同二叉树的数目由于二叉树是递归地定义的, 所以我们很自然地得到关于 B n 的递归方程 : B n =1 n 1 当 n=0 B n = 当 n>0 i = 0 B ib n i 1 即一棵具有 n>1 个结点的二叉树可以看成是由一个根结点一棵具有 i 个结点的左子树和一棵具有 n-i-1 个结点的右子树所组成求得 :B n = C n 2 n n + 1

94 6.7 哈夫曼树哈夫曼树的定义设二叉树具有 n 个带权值的叶子结点, 那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和, 称为二叉树的带权路径长度 n WPL = 1 i= w i l i 其中 n 表示叶子结点的数目,w i 和 l i 分别表示叶子结点 k i 的权值和根结点到 k i 之间的路径长度 ( 即从根结点到达叶子结点的分支数 ) 具有最小带权路径长度的二叉树称为哈夫曼树

95 相同的叶子结点构造出不同的二叉树 WPL(T)= =60 WPL(T)= =89

96 6.7.2 构造哈夫曼树根据哈夫曼树的定义, 一棵二叉树要使其 WPL 值最小, 必须使权值越大的叶子结点越靠近根结点, 而权值越小的叶子结点越远离根结点构造一棵哈夫曼树的方法如下 : (1) 给定的 n 个权值 {W 1,W 2,...,W n } 构造 n 棵只有一个叶子结点的二叉树, 从而得到一个二叉树的集合 F={T 1,T 2,...,T n }; (2) 在 F 中选取根结点的权值最小和次小的两棵二叉树作为左右子树构造一棵新的二叉树, 这棵新二叉树的根结点的权值为其左右子树根结点权值之和 ; (3) 在集合 F 中删除作为左右子树的两棵二叉树, 并将新建立的二叉树加入到集合 F 中 ; (4) 重复 (2) (3) 两步, 当 F 中只剩下一棵二叉树时, 这棵二叉树便是所要建立的哈夫曼树

97 用 ht[] 数组存放哈夫曼树,n 个叶子结点的哈夫曼树共有 2n-1 个结点树中每个结点结构如下 : typedef struct { char data; // 结点值 float weight; // 权重 int parent; // 双亲结点 int lchild; // 左孩子结点 int rchild; // 右孩子结点 } HTNode;

98 其算法思路是 : 1. n 个叶子结点只有 data 和 weight 域值, 先将所有 2n-1 个结点的 parent lchild 和 rchild 域置为初值处理每个非叶子结点 ht[i]( 存放在 ht[n]~ht[2n-2] 中 ): 从 ht[0] ~ht[i-1] 中找出根结点 ( 即其 parent 域为 -1) 最小的两个结点 ht[lnode] 和 ht[rnode], 将它们作为 ht[i] 的左右子树,ht[lnode] 和 ht[rnode] 的双亲结点置为 ht[i], 并且 ht[i].weight= ht[lnode].weight+ht[rnode].weight 3. 如此操作直到所有 n-1 个非叶子结点处理完毕

99 6.8.3 哈夫曼编码具体构造方法如下 : 设需要编码的字符集合为 {d 1,d 2,,d n }, 各个字符在电文中出现的次数集合为 {w 1,w 2,,w n }, 以 d 1,d 2,,d n 作为叶结点, 以 w 1,w 2,,w n 作为各根结点到每个叶结点的权值构造一棵二叉树规定哈夫曼树中的左分支为 0, 右分支为 1, 则从根结点到每个叶结点所经过的分支对应的 0 和 1 组成的序列便为该结点对应字符的编码这样的编码称为哈夫曼编码

100 :0000 5: :001 7:1110 8: :01 29:10 14:110

101 本章小结本章的基本学习要点如下 : (1) 掌握树的相关概念, 包括树结点的度树的度分支结点叶子结点儿子结点双亲结点树的深度森林等定义和树的表示法 (2) 掌握二叉树的概念和性质, 包括二叉树满二叉树和完全二叉树 (3) 重点掌握二叉树的存储结构, 包括二叉树顺序存储结构和链式存储结构 (4) 重点掌握二叉树的基本操作和各种遍历算法的实现 (5) 掌握哈夫曼树的定义哈夫曼树的构造过程和哈夫曼编码产生方法 (6) 灵活运用二叉树这种数据结构解决一些应用问题

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用