数据结构--(6)课件

1、6.1 树的基本概念和术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 二叉树、 树和森林6.6 树的应用6.7 二叉树的建立和遍历C语言源程序示例第6章树返回主目录第6章 树 6.1 树的基本概念和术语 6.1.1 树的定义树（tree）是由一个或多个结点组成的有限集合T。 其中: (1) 有一个特定的结点称为该树的根（root）结点; (2) 除根结点之外的其余结点可分为m（m0）个互不相交的有限集合T1, T2, , Tm, 且其中每一个集合本身又是一棵树, 称之为根的子树（subtree）。 这是一个递归的定义, 即在定义中又用到了树这个术语。 它反应了树的固有特性。可以认

2、为仅有一个根结点的树是最小树, 树中结点较多时, 每个结点都是某一棵子树的根。 图6.1是一棵由 11 个结点组成的树T。 其中A是根结点, 其余结点分为三个互不相交的子集: T1 =B,E,F, T2 =C,G, T3 =D,H,I,J,K。 T1、 T2 、 T3都是树根的子树, 这三棵子树的根结点分别是B、 C、 D。每棵子树本身也是一棵树, 可继续划分。 例如子树T3以D为根结点, 它的其余结点又可分为三个互不相交的子集: T31=H, T32=I,K, T33 = J, 而其中T31 、 T33都可认为是仅有一个根结点的子树。 6.1.2 树的常用术语树结构常常用到一些术语, 如度、

3、 双亲、 孩子、 树深等。 结点的度是结点的子树的个数。树的度是树中结点度的最大值。度为零的结点称为叶子或终结点。度不为零的结点称为非终端结点。图6.1中树T的度为。结点E, F, G, H, K, J度为零, 它们是叶子结点。 某结点的各子树的根结点称为该结点的孩子, 而该结点又称为孩子们的双亲结点。具有相同双亲的结点互称为兄弟。图6.1中根结点A有三棵子树, 这三棵子树的根结点分别是B, C, D, 因此说结点A是结点B, C, D的双亲, 而结点B, C, D又都是结点A的孩子, B, C, D之间互为兄弟。 一棵树上除根结点以外的其它结点称为根结点的子孙。 对于树中某结点, 从根结点开

4、始到该结点的双亲是该结点的祖先。 结点的层次值从根算起, 根的层次值为, 其余结点的层次值为双亲结点层次值加。一棵树的深度是该树中结点最大层次值, 例如图6.1中的树T的深度为。结点A、B、E、K的层次值分别为1、 2、 3、 4。 6.1.3 树的表示方法 树的表示形式有多种, 常见的三种方法是: (1) 倒悬树法, 如图6.1所示。 (2) 集合包含关系文氏图法, 如图6.2(a)所示。 (3) 凹入法, 如图6.2(b)所示。 6.2 二叉树 6.2.1 二叉树的定义 二叉树（binary tree）是n（n=0）个结点的有限集合。 它或为空树（n=0）, 或为非空树; 对于非空树有:

5、(1) 有一个特定的称之为根的结点。 (2) 除根结点以外的其余结点分为两个互不相交的称之为左子树和右子树的二叉树构成。 这个定义是递归的。由于左、 右子树也是二叉树, 因此子树也可为空树。 图6.3中展现了五种基本形态不同的二叉树。 6.2.2 二叉树的重要性质 性质1二叉树第i(i1)层上至多有2 i-1个结点。 根据图6.4(a)可知, 根结点在第一层上, 这层结点数最多为1个, 即20个; 显然第二层上最多有2个结点, 即21个; 假设第i-1层的结点最多有2 i-2个, 且每个结点最多有两个孩子, 那么第i层上结点最多有 2* 2 i-2= 2 i-1个。 性质2深度为k(k1)的二

6、叉树至多有2 i-k个结点。 由性质1可知各层结点最多数目之和为 20 + 21+ 22+ 2 k-1; 由二进制换算关系可知: 20+ 21+ 22+ 2k-1 = 20, 因此二叉树树中结点的最大数目为20。 性质3在任意二叉树中, 若叶子结点（即度为零的结点）个数为n0, 度为1的结点个数为n1, 度为2的结点个数为n2, 那么 n0 = n2+1。 设n代表二叉树结点总数, 那么 n = n0 + n1 + n2 (6.1) 由于有n个结点的二叉树总边数为n-1条, 于是得 n-1=0* n0 +1* n1+2* n2 (6.2) 将式(6.1)代入式(6.2)得 n0= n2+1 有

7、两种特殊形态的二叉树, 它们是满二叉树和完全二叉树。 深度为k并且含有2k-1个结点的二叉树称为满二叉树, 这种树的特点是每层上的结点数都是最大结点数, 如图6.4(a)所示。对满二叉树的结点可以从根结点开始自上向下, 自左至右顺序编号, 图6.4(a)中每个结点斜上角的数字即是该结点的编号。 深度为k, 含有n个结点的二叉树, 当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时, 则称此二叉树为完全二叉树, 如图6.4(b)所示。 而图6.4(c)则不是完全二叉树。 质4具有n个结点的完全二叉树树深为 log2n+1（其中x表示不大于x的最大整数）。 性质5若对有n个结点的完全

8、二叉树进行顺序编号(1in), 那么, 对于编号为i(i1)的结点: 当i=1时, 该结点为根, 它无双亲结点; 当i1时, 该结点的双亲结点编号为i/2; 若2in, 则有编号为2i的左孩子, 否则没有左孩子; 若2i+1n, 则有编号为2i+1的右孩子, 否则没有右孩子。 对照图6.4(a)或图6.4(b), 读者可看到由性质所描述的结点与编号的对应关系。 6.2.3 二叉树的存储结构 二叉树常用的存储结构有两种, 顺序存储结构（向量）和链表存储结构。 (1) 顺序存储结构（向量）可以作为二叉树的存储结构。 这种存储结构适用于完全二叉树、满二叉树。假设用一维数组a存放图6.4(a)的满二叉

9、树。可以发现图6.4(a)中结点的编号恰好与数组元素的下标相对应, 见图.5。根据二叉树性质5, 在a数组中可以方便地由某结点ai的下标i找到它们的双亲结点ai/2或左、 右孩子结点a2i、 a2i+1。在哈夫曼树构造算法中也用到顺序存储结构。一般二叉树较少采用顺序存储结构。 (2) 链表存储结构通常用于二叉树存储。 常见的有二叉链表和三叉链表。二叉链表的每个结点都有一个数据域和两个指针域, 一个指针指向左孩子, 另一个指针指向右孩子。结点结构描述为: struct node int data; WB/* 数据域 */ struct node *lch, *rch; /* 左、 右指针域 */

10、 三叉链表的结点比前者多了一个指向双亲的指针域。 结点结构描述为: struct node3 int data; /* 数据域 */ struct node *lch, *parent, *rch; /* par是双亲指针域 */ 对于图6.6(a)中二叉树T, 它的二叉链表如图6.6(b), 三叉链表如图6.6(c)。 6.2.4 二叉树二叉链表的一个生成算法 此方法主要利用二叉树的性质5。 对任意二叉树, 先按满二叉树对其进行编号, 如图6.7(a)所示。由于此树并非完全二叉树, 所以编号并不连续。 算法中使用一个辅助向量s用于存放 指向树结点的指针, 如si中存放编号为i的结点的指针,

11、即为该结点的地址。 此例原始数据序列如图6.7(b)所示, 照此一一输入即可生成二叉链表。 当结点编号i=1时, 所产生的结点为根结点, 同时将指向该结点的指针存入s1。当结点编号i1时, 产生一个新的结点之后, 也要将指向该结点的指针存入si。 由性质5可知: j=i/2 为它的双亲结点编号。 如果i为偶数, 则它是双亲结点的左孩子, 即让sj-lch = si; 如果i为奇数, 则它是双亲结点的右孩子, 即让sj-rch = si。这样就将新输入的结点逐一与其双亲结点相连, 生成二叉树。 结点结构如前所描述, 为struct node 。 辅助向量为 struct node *s20。 二

12、叉树生成算法如算法6.1。 算法 6.1 算法 6.1 stuct node *creat( ) printf(i, x=); scanf(%d%d, &i, &x); while (i!KG-*2=0)&(x!KG-*2=0) q=(struct node*)malloc(sizeof(struct node)/* 产生一个结点 */ q-data=x; q-lch=NULL; q-rch=NULL; si=q; if (i=1) t=q; /* t 为部局变量, 代表树根结点 */ else j=i/2; /* 双亲结点编号 */ if (i%2)=0) sj-lch=q; else sj

13、-rch=q; printf(i, x=); scanf(%d%d, &i, &x); return(t) /* creat end */6.3 遍 历 二 叉 树 前已经指出, 对于二叉树经常采用链表做为它的存储结构, 本节及以后对二叉树的讨论将主要针对链表存储结构来进行 遍历二叉树是指以一定的次序访问二叉树中的每个结点, 并且每个结点仅被访问一次。 所谓访问结点是指对结点进行各种操作的简称。 例如, 查询结点数据域的内容, 或输出它的值, 或找出结点位置, 或是执行对结点的其它操作。 遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时, 访问结点的操作就是输出结点数据

14、域的值, 那么遍历的结果得到一个线性序列。由于二叉树有左、右子树, 所以遍历的次序不同, 得到的结果就不同。 令L、 T、 R分别代表遍历左子树、 访问根结点和遍历右子树, 则对一棵二叉树的遍历可以有六种不同次序: LTR, LRT, TLR, TRL, RLT, RTL。 然而经常用到的总是先左（L）后右（R）, 若再把访问根结点（T）的操作穿插其中, 则只有三种不同的遍历次序: LTR、 TLR 和 LRT。 它们分别称作中根遍历、 先根遍历和后根遍历二叉树。 在介绍常用的三种遍历算法之前, 首先介绍一下遍历的具体方法。例如有一棵二叉树有4个结点。 为了便于理解遍历的思想, 暂且为每个没有

15、子树的结点均补充上相应的空子树, 用来表示, 见图6.8。设想有一条搜索路线（用虚线表示）, 它从根结点的左侧开始, 自上而下自左至右搜索, 最后由根结点右侧向上出去。 不难看出, 若考虑到空子树的话, 恰好搜索路线途经每个有效的树结点都是三次。把第一次经过就访问的结点列出, 它们是A、 B、 C、 D, 这就是先根遍历的结果。 那么第二次经过才访问的则是中根遍历, 其结果是B、A、 D、C。第三次经过才访问的是后根遍历, 结果是B、D、C、 A。 二叉树的链表存储, 其结点结构定义如下: struct node char data; /* 假设数据类型char, 根据需要也可为其它类型 */

16、 struct node *lch, *rch; 6.3.1 先根遍历 先根遍历可以递归的描述如下: 如果根不空: (1) 访问根结点; (2) 按先根次序遍历左子树; (3) 按先根次序遍历右子树; 否则返回。 先根遍历的递归算法如算法6.2。 算法 6.2 Void preorder(struct node *p) if (p!KG-*2NULL) printf (6ct”, p-data); /* 访问根结点 */ preorder(p-lch); /* 按先根次序遍历左子树 */ preorder(p-rch); /* 按先根次序遍历右子树 */ /* preorder */ 现在针对

17、图6.8中的二叉树, 对递归算法的详细执行情况进行分析, 如图6.9所示。 图6.8中树深度为3, 递归调用的深度为4层。 这就是在遇到空的子树时, 它也调用了一次preorder函数, 只不过是因为子树的根为空立即返回而已。 还应注意对某根结点访问之后, 便对其左子树进行先根遍历, 随即进入下一层递归调用, 当返回本层调用时, 仍以本层根结点为基础对其右子树进行先根遍历。 当从下一层递归调用（先根遍历右子树）再次返回本层时, 接着就从本层调用返回到前一层调用。依此类推, 最终返回主调程序。 6.3.2 中根遍历 中根遍历递归的思路与先根遍历十分相似, 只是在根不空的情况下所应执行的三条操作稍

18、做调整即可。具体来说, 也就是把第(1)条与第(2)条进行对换。 中根遍历可以递归的描述如下: 如果根不空: (1) 按中根次序遍历左子树; (2) 访问根结点; (3) 按中根次序遍历右子树; 否则返回。 中根遍历递归算法如算法6.3。 算法 6.3 Void inorder( struct node *p) if (p! NULL) inorder(p-lch); /* 中根遍历左子树 */ printf(6ct”, P-data); /* 访问根结束 */ inorder(p-rch); /* 中根遍历右子树 */ /* inorder */ 此递归算法的具体执行情况, 请读者自己分析。

19、 中根遍历非递归算法如算法6.4。 算法 6.4 Void inorderz(struct node *p) /* 栈s是 struct node *s10 */ qp; top0; /* 栈顶指针 */ bool1; JY/* bool=1为真值继续循环; bool=0为假值栈空, 结束循环*/ do while (q! NULL) top; stopq; qq-lch; if (top=0) bool0; else qstop; top- -; printf(6ct”, q-data); /* 访问根结点 */ qq-rch; while (bool); /* inorderz */ 对照

20、图6.8中的二叉树, 在中根非递归遍历过程中其栈s的内容变化如图6.10所示。 假设二叉树有个结点, 对每个结点都要进行一次入栈和出栈操作, 即入栈和出栈各执行n次, 对结点的访问也是n次, 此算法的时间复杂度为O(n)。 所需栈的空间最多等于二叉树深k乘以每个结点所需空间数, 可以记作O(k)。 如果要写先根遍历非递归算法, 在搞清中根遍历非递归方法后, 不难看出只要将访问语句移一位置便可实现。 6.3.3 后根遍历 在搞清楚先根遍历、 中根遍历递归方法之后, 可以看出, 只要将访问根结点的语句移至遍历左子树、右子树的语言后面即可得出后根遍历递归算法。后根遍历递归算法的描如下: 如果根不空:

21、 (1) 按后根次序遍历左子树; (2) 按后根次序遍历右子树; (3) 访问根结点; 否则返回。 后根遍历递归算法如算法6.5。 算法 6.5 Void postorder(stuct node *p) if (p!KG-*2NULL) postorder(p-lch); /* 后根遍历左子树 */ postorder(p-rch); /* 后根遍历右子树 */ printf(6ct”, p-data); /* 访问根结点 */ /* postorder */ 后根遍历的非递归算法较为复杂, 不仅在搜索线第一次经过根结点时不访问并且进栈, 而且在后根遍历它的左子树之后, 搜索线第二次经根结点

22、时也不能访问。因此, 在搜索线第二次经根结点时不能让栈顶元素（根）出栈, 而是依据栈顶元素所表示的根去后根遍历它的右子树; 直到搜索线第三次经过这个根结点时, 才将其出栈, 并且访问这个根结点。 因此, 另需一个辅助栈2用来记录经过某根结点的次数。 两个栈的类型为: struct node *s10; int s220。 后根遍历的非递归算法如算法6.6。 算法 6.6 Void postorderz (stuct node *p) qp; top0; bool1; do while (q! NULL) top+; stopq; s2top1; qq-lch; if (top=0) bool0

23、; else if(s2top=1) s2top2; /* 第二次经过, 不退栈 */ qstop; qq-rch; else qstop; /* 第三次经过, 退栈并且访问根结点 */ s2top0; top-; printf(6ct”, q-data); qNULL; while (bool); /* postorder2 */ 算法6.7 viod levelorder(struct node *p) struct node *q20; /* 辅助队列, 假设树结点不超过19个 */ front=0; rear=0; /* 置空队列 */ if(p!KG-*2=NULL) rear+;

24、qrear=p; /* 根结点进队 */ while(front!KG-*2=rear) /* 队首结点出队并且访问 */ front+; p=qfront; printf(6ct”, t-data); if(p-lch!-=NULL) rear+; qrear=p-lch; /* P左孩子不空则进队 */ if(p-rch!KG-*2=NULL) rear+; qrear=p-rch; /* P右孩子不空则进队 */ /* 当队列不空时, 继续循环 */ /* levelorder end */ 6.3.4 二叉树遍历算法的应用 1. 统计二叉树中结点个数m和 叶子结点个数n 分析: 在调用

25、遍历算法时设两个计数器变量m、n。我们知道所谓遍历二叉树, 即以某种次序去访问二叉树的每个结点, 且每个结点仅访问一次, 这就提供了方便的条件。每当访问一个结点时, 在原访问语句printf后边, 加上一计数器语句m+和一个判断该结点是否为叶子的语句, 便可解决问题。在这里, 所谓访问结点的操作拓宽为一组语句, 见下列算法中的第4、 5、 6行。 假设用中根遍历方法统计叶子结点的个数, 算法如算法6.8。 算法 6.8 Void injishu(struct node *t) if (t!KG-*2=NULL) injishu(t-lch); /* 中根遍历左子树 */ printf(“6ct

26、”, t-data); /* 访问根结点 */ m+; /* 结点计数 */ if(t-lch=NULL)&(t-rch=NULL) n+; /* 叶子结点计数 */ injishu(t-rch); /* 中根遍历右子树 */ /* injishu */ 该函数中的printf(“6ct”, t-data)语句输出格式是针对图6.8设计的。 如果数据域类型不是字符型而是整型, 语句应该为printf(“6dt”, t-data)。 假设数据域类型更为复杂, 就应结合具体实际重新设计输出模块。上面函数中m、 n是全局变量, 在主程序先置零, 在调用injishu函数结束后, m值便是结点总个数,

27、 n值便是叶子结点的个数。主函数示意 如下: main( ) t=creat( ); /* 建立二叉树t, 为全局变量 */ m=0, n=0; /* 全局变量m, n置初值 */ injishu(t); /* 求树t中结点总数m, 叶子结点的个数n */ printf(m=%4d, n=%4d, m , n); /* 输出结果 */ 2. 求二叉树的树深 首先看如下算法。 算法6.9 Void predeep(struct node *t, int i) if (t! NULL) printf(“6ct”, tdata); /* 访问根结点 */ i+; if(kltag0; (2) p无左

28、孩子时, 令p-ltag1, 并且p-lch指向p的前趋结点; (3) p有右孩子时, 令p-rtag0; (4) p无右孩子时, 令p-rtag1, 并且让p-rch指向p的后继结点。 针对图6.11(a)的二叉树, 它的中根次序线索树的链表表示如图6.11(b)所示。 线索用带箭头的虚线表示。 6.4.2 线索二叉树的逻辑表示图 按照不同的遍历次序进行线索化, 可得到不同的线索二叉树。有先根线索二叉树、中根线索二叉树和后根线索二叉树。 对图6.12(a)的二叉树线索化, 可得到图6.12(b)、(c)、(d)三种线索二叉树的逻辑表示。 读者应能熟练掌握三种不同的线索二叉树的逻辑图画法。 画

29、图时应注意, 线索要画成带箭头的虚线, 应从结点的左下方和右下方出发, 左右分明, 指向准确。 6.4.3 中根次序线索化算法 1. 中序（中根次序）线索化递归算法 中序(中根次序)线索化递归算法如算法6.10。 算法 6.10 Void inthread(struct nodex *p) if (p!=NULL) inthread(p-lch); printf (6ct”, p-data); if (plc!=NULL) p-ltag=0; elsep-ltag=1; p-lch=pr; /* 建p结点的左线索, 指向前趋结点pr */ if (pr!=NULL) if (pr-rch!=N

30、ULL) pr-rtag=0; else pr-rtag=1; pr-rch=p; /* 前趋结点pr建右线索, 指向结点p */ZK) pr=p; /* pr跟上p, 以便p向后移动 */ inthread(p-rch); /* inthread */ 此算法中pr是全局变量, 在主程序中置初值为空。 在inthread函数中pr始终做为当前结点p的前趋结点的指针。在线索化过程中, 边判断二叉树的结点有无左、右孩子, 边给相应标志域置0或1, 边建立线索。 在阅读此算法时, 将inthread(p-lch)和inthread(p-rch)之间的一组语句看成一个整体, 把这段语句理解为“访问”

31、, 很明显这里应用了典型的中根遍历算法思路。 在递归调用结束时p为空, 这表明pr已是最后一个结点, 应该没有后继结点。 所以在返回主程序后还要使prrchNULL, 至此整个线索化结束。主函数语句示意如下: 初学者在这里往往易犯错误, 常把预处理pr=NULL和善后处理pr-rchNULL放在线索化子函数Void inthread (struct nodex *p)中, 一个放最前边, 另一个放最后边。这样每递归调用一次, pr就置一次空, 无法记下p的前驱结点。而在从深度递归返回时, 每返回一次就让pr-rch置一次空, 这显然是错误的。 因此, 在描述递归算法时, 提倡同时写出主函数来示

32、意递归调用前的初始化处理和递归调用结束后的善后处理。 main( ) pr=NULL; /* 全局变量 */ t=creat( ); /* 建立二叉树 */ inthread(t); /* 中序线索化二叉树 */ pr-rchNULL; /* 善后处理 */ 2. 中序线索化非递归算法 在这里需借用一个辅助结构栈 struct nodex *s20, 如算法6.11。 算法 6.11 Void inthread2(struct nodex *t) pr=NULL; p=t; top=0; bool=1; KG6/* bool为真值 */ do while (p!=NULL) top+; sto

33、p=p; p=p-lch; if (top=0) bool=0; /* 栈空, bool置假值 */ else p=stop; top-; printf(6ct, p-data); if (p-lch!=NULL) p-ltag=0; else p-ltag=1; p-lch=pr; /* 建p结点的左线索, 指向前趋结点pr */ if (pr!=NULL) if (pr-rch!=NULL) pr-rtag=0; else pr-rtag=1; pr-rch=p; /* 前趋结点pr建右线索, 指向结点p */ 在这个非递归算法中, pr仍做为p结点的前趋结点指针。 pr初值置NULL以及

34、pr-rch置NULL, 分别放在这个函数的开头和结尾。这是与递归算法处理不同的地方。如果把算法中第819行的语句组看成“访问”操作, 显然是利用了中根非递归遍历思路。 非递归中根线索化算法的时间复杂度和空间占用量与非递归中根遍历二叉树的算法是一样的。pr=p; p=p-rch; /* else */ while (bool); pr-rchnull; ZK) /* inthread2 */ 6.4.4 在中根线索树上检索某结点的前趋或后继 (1) 已知q结点, 找出它的前趋结点。 根据线索树的基本概念, 当q-ltag1时, q-lch就指向q的前趋。 当q-ltag=0时, 表明q有左孩子

35、。 由中根遍历的规律可知, 做为根q的前趋结点(或者说以根结点为后继的结点), 它应是中根遍历q的左子树时访问的最后一个结点, 即左子树的最右尾结点。 请看图6.12(b), 结点D是A的左子树的最右尾结点, 它就是A的前趋结点。 而D的后继指针指向了A, A就是D的后继结点。 若用p记录q的前趋, 算法如算法6.12。 算法 6.12 struct nodex *inpre(struct nodex *q) if(q-ltag=1) p=q-lch; else r=q-lch; while (r-rtag!KG-*3=1) r=r-rch; p=r; return(p); (2) 已知q结点

36、, 找出它的后继结点。 当q-rtag1时, q-rch即指向q的后继结点。 若q-rtag0, 表明q有右孩子, 那么q的后继应是中序遍历q的右子树时访问的第一个结点, 即右子树的最左尾结点。看图6.12(c), A的后继为F, C的后继为H。 若用p记录q后继结点, 算法如下: struct nodex*insucc(struct nodex *q) if(q-rtag=1) p=q-rch; else r=q-rch; while (r-ltag!=1) r=r-lcg; p=r; return(p); 6.4.5 在中根线索树上遍历二叉树 算法6.13 void inthorder(s

37、tuct nodex *t) p=t; if(p! =NULL) while(p-lch!KG-*3=NULL) p=p-lch; /* 查找二叉树的最左结点 */ printf(6c”, p-data); while(p-rch!KG-*3=NULL) p=insucc(p); /* 调用求某结点p后继的算法 */ printf(6c”, p-data); /* inthorder */ 6.5 二叉树、树和森林 6.5.1 树的存储结构 树的存储结构有顺序结构和链表结构。 顺序存储结构即向量, 一般将树结点按自上而下, 自左至右的顺序一一存放。 如前文所介绍的完全二叉树就可以采用顺序存储结

38、构。对于一般树结构更适合使用链表存储结构。常用的有: 结点定长的多叉链表和孩子兄弟二叉链表。 图6.13所示的树是一个三叉树, 可用三重链表来存储, 其结点结构为: 有一个数据域和三个指针域, 指针域用于指向该结点的各个孩子。 该树的三重链表如图6.14（a)所示。 如果用孩子-兄弟链表作存储结构, 其结点结构为: 有一个数据域和两个指针域, 一个指针指向它的长子, 另一指针r指向它的一个兄弟。 孩子兄弟链表如图6.14(b)所示。 假设把图6.14(b)中指向兄弟的水平方向指针改为下斜45, 不难发现它与一棵二叉树十分相似。由本章6.2节可知二叉树的结构规范、 简单并具有一些重要的性质, 因

39、此常将一般树结构转换为二叉树结构进行处理。 6.5.2 树与二叉树之间的转换 对于一般树, 树中孩子的次序并不重要, 只要双亲与孩子的关系正确即可。 但在二叉树中, 左、 右孩子的次序是严格区分的。 所以在讨论二叉树与一般树之间的转换时, 为了不引起混淆, 就约定按树上现有结点次序进行转换。 1. 一般树转化为二叉树 将一般树转化为二叉树的思路, 主要根据树的孩子-兄弟存储方式而来, 步骤是: (1) 加线: 在各兄弟结点之间用虚线相链。 可理解为每个结点的兄弟指针指向它的一个兄弟。 (2) 抹线: 对每个结点仅保留它与其最左一个孩子的连线, 抹去该结点与其它孩子之间的连线。可理解为每个结点仅

40、有一个孩子指针, 让它指向自己的长子。 (3) 旋转: 把虚线改为实线从水平方向向下旋转45, 成右斜下方向。原树中实线成左斜下方向。这样就形成一棵二叉树。 由于二叉树中各结点的右孩子都是原一般树中该结点的兄弟, 而一般树的根结点又没有兄弟结点, 因此所生成的二叉树的根结点没有右子树。在所生成的二叉树中某一结点的左孩子仍是原来树中该结点的长子, 并且是它的最左孩子。图6.15是一个由一般树转为二叉树的实例。 2. 二叉树还原为一般树 二叉树还原为一般树, 此时的二叉树必须是由某一树转换而来的没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。 其还原过程也分为三步: (1) 加线: 若某结

41、点i是双亲结点的左孩子, 则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子, 都分别与结点i的双亲结点用虚线连接。 (2) 抹线: 把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟, 抹去的连线是兄弟间的关系。 (3) 进行整理: 把虚线改为实线, 把结点按层次排列。 二叉树还原为一般树的示例, 如图6.16所示。 6.5.3 森林与二叉树的转换 森林是树的有限集合, 如图6.17(a)所示。 1. 森林转换为二叉树 森林转换为二叉树的步骤为: (1) 将森林中每棵子树转换成相应的二叉树， 形成有若干二叉树的森林。 (2) 按森林

42、图形中树的先后次序, 依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树, 这样整个森林就生成了一棵二叉树, 实际上第一棵树的根结点便是生成后的二叉树的根结点。 图6.17是森林转化为二叉树的示例。 图6.17 森林转换为二叉树(a) 一般树的森林； (b) 二叉树的森林； (c) 第二棵子树并入第一棵子树； (d) 最终结果 2. 二叉树还原为森林 将一棵由森林转换得到的二叉树还原为森林的步骤是: (1) 抹线: 将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去, 这样就得到包含有若干棵二叉树的森林。 (2) 还原: 将每棵二叉树按二叉树还原

43、一般树的方法还原为一般树, 于是得到森林。 这部分的图示, 请读者自己练习画出。 6.5.4 一般树或森林的遍历 一般树的遍历主要是先序和后序遍历, 一般不讨论中序遍历。 树的先序遍历首先访问树的根结点, 然后从左至右逐一先序遍历每一棵子树。 树的后序遍历首先后序遍历树的最左边的第一棵子树, 接着从左至右逐一后序遍历每一棵子树, 最后访问树的根结点。 由于一般树转换为二叉树后, 此二叉树没有右子树, 对此二叉树的中序遍历结果与上述一般树的后序遍历结果相同。 因此, 有的教科书中把一般树的后序遍历称为中序遍历。一般树的孩子-兄弟链表存储结构如下: struct nodet int data; s

44、truct nodet *child, *brather; (1) 利用一般树的孩子-兄弟链表存储结构, 先序遍历该树的算法如算法6.14。 算法6.14 Void preordertre(struct nodet *root) /* root 一般树的根结点 */ /* s30是辅助栈 */ qroot; top0; /* 栈顶指针 */ bool1; /* bool=1为真值继续循环; bool=0为假值栈空, 结束循环*/ do while (q! NULL) printf(6d”, q-data); /* 访问根结点 */ top; stopq; qq-child; /* 搜索根结点的

45、第一个孩子结点 */ if (top=0) bool0; else qstop; top-; qq-brather; /* 对出栈后的结点找它的下一个兄弟结点 */) while (bool); printf( n); /* preordertre */ (2) 利用森林转换成的二叉树, 按层遍历该森林的算法如算法6.15。 算法6.15 Void leveltraverse(struct node *root) struct node *q20; /* 辅助队列, 假设树结点不超过19个 */ front=0; rear=0; /* 置空队列 */ p=root; if(p!=NULL) r

46、ear+; qrear=p; /* 根结点进队 */ while(front!KG-*3=rear) front+; p=qfront;/* 队首结点出队 */ While(p! =NULL) printf(6c, t-data); if(p-child!KG-*3=NULL) rear+; /* P第一个孩子不空则进队 */ qrear=p-child; p=p-brather;/* 找p的下一个兄弟结点 */ /* 当队列不空时, 继续循环 */ /* leveltraverse end */ 6.6 树的应用 6.6.1 二叉排序树 1. 二叉排序树的定义和特点 定义: 二叉排序树(bi

47、nary sort tree)或是空树; 或是非空树 。 对于非空树: （1） 若左子树不空, 则左子树上各结点的值均小于它的根结点的值; （2） 若右子树不空, 则右子树上各结点的值均大于等于它的根结点的值; （3） 它的左、 右子树又分别是二叉排序树。 例如图6.18所示为一棵二叉排序树。 特点: 对二叉排序树进行中序遍历, 可得到一个由小到大的序列。 例如, 对图6.18的二叉排序树进行中根遍历, 则得到序列: 2, 3, 6, 8, 9, 10, 15, 18, 19。 2. 建立二叉排序树的算法建立二叉排序树, 实质上是不断地进行插入结点的操作。 设有一组数据:=k1 k2 , ,

48、kn , 将它们一一输入建成二叉排序树。 我们用二叉链表做为存储结构。 结点结构如下: struct nodb int data; struct nodb *lch, rch; 思路分析: (1) 让k1做根; (2) 对于k2, 若k2 k1, 令k2做k1的左孩子; 否则令k2做k1的右孩子; (3) 对于k3, 从根k1开始比较。 若k3 k1 ，到左子树中找； 否则到右子树中找；找到适当位置进行插入； (4) 对于k4, k5, , kn, 重复第(3)步, 直到kn处理完为止。 在建立过程之中, 每输入一个数据元素, 就插入一次。 现把插入一个结点的算法单独编写, 而在建立二叉排序树

49、的函数中对其进行调用。 首先看建立二叉排序树的主体算法: 算法 6.16struct nodb creat( ) Printf(n?); scanf(d, n ); t=NULL; for(i=1; idatak; s-lchNULL; s-rchNULL; insert1(t, s); /* 或调用insert2(t, s) */ return(t); 在二叉排序树中, 插入一个结点s的递归算法: 算法 6.17Void insertl(struct nodb *t, struct nodb *s) if(t=NULL) t=s; else if(s-data t-data)insert1(

50、t-lch, s ); /* 将s插入t的左子树 */ else insert1(t-rch, s); /*将s插入t的右子树 */ 在二叉排序树中, 插入一个结点s的非递归算法: 算法 6.18Void insert2(styoct nodb *t, struct nodb *s) if(t=NULL) t=s; else p=t; while(p!KG-*3=NULL) qp; /* 当P向子树结点移动时, q记P的双亲位置 */ if(s-data p-data) pp-lch; else pp-rch; if(s-data q-data) q-lch=s; else q-rch=s;

51、/*当p为空时, q就是可插入的地方*/ 假设给出一组数据10, 3, 18, 6, 20, 2, 对照上述算法生成二叉排序树的过程如图6.19所示。 由此可见, 在二叉排序树上插入结点不需要遍历树, 仅需从根结点出发, 走一条根到某个有空子树的结点的路径, 使该结点的空指针指向被插入结点, 使被插入结点成为新的叶子结点。 如果仍使用前边6个数据, 但输入先后顺序改为2, 3, 6, 10, 18, 20, 那么生成的二叉排序树如何？请思考。 3. 在二叉排序树中删除结点在二叉排序树上删除一个结点, 应该在删除之后仍保持二叉排序树的特点。要删除某结点p, p结点和它的双亲结点f都是已知条件,

52、这里的关键是怎样找一个结点s来替换p结点。 下面分三种情况来讨论。 (1) p结点无右孩子, 则让p的左孩子s上移替代p结点， 如图6.20(a)、 (b)所示。 (2) p结点无左孩子, 则让p的右孩子s上移替代p结点， 如图6.20(c)、 (d)所示。 (3) p结点有左孩子和右孩子, 可用它的前趋（或后继）结点s代替p结点。现假定用它的后继结点来代替, 这个结点s应是p的右子树中数据域值最小的结点, 或者说是p的右子树中最左结点。 因其值域最小(在右子树中)， 所以它一定没有左孩子。 这时先让p结点取s结点的值, 然后可按第(2)种情况处理删除s结点, 这就等效删除了原p结点。 如图6

53、.20(e)所示。 参见算法6.19, 其中t, f, p为已知条件, t指向根结点, f指向p的双亲, p指向被删除结点。 另设s, q指针, 分别指向替代结点及其双亲。 算法6.19Void delet(struct node *t, struct node *p, struct node *f) bool1; if(p-lch=NULL) sp-rch; else if (p-rch=NULL) sp-lch; else q=p; sp-rch; /* p左, 右孩子均 不空的情况 */ while(s-lch ! =NULL) qs; ss-lch; if (q=p) q-rchs-r

54、ch; else q-lchs-rch; p-datas-data; free(s); bool0; /* 删除完成 */ if (bool=1) /* p不是有左, 右两个孩子的情况 */ if(f=NULL) ts; /* f=NULL即是p=t情况 */ 6.6.2 哈夫曼树及其应用 哈夫曼树（Huffman）, 又称最优二叉树, 是一类带权路径长度最短的树, 有着广泛的应用。 1. 哈夫曼树的基本概念 在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念。 树中两个结点之间的路径由一个结点到另一结点的分支构成。 两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个

55、结点的路径长度之和。 设一棵二叉树有n个叶子结点, 每个叶子结点拥有一个权值1,2, ,n, 从根结点到每个叶子结点的路径长度分别为L1, L2, Ln, 那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和， 通常记作: 为了直观起见, 在图中把带权的叶子结点画成方形, 其它非叶子结点仍为圆形。请看图6.21中的三棵二叉树以及它们的带权路径长。 请注意, 这三棵二叉树叶子结点数相同, 它们的权值也相同, 但是它们的WPL带权路径长各不相同。 图6.21(c)WPL最小。 它就是哈夫曼树, 最优树。哈夫曼树是在具有同一组权值的叶子结点的不同二叉树中, 带权路径长度最短的树也称最优树。

56、2. 哈夫曼树的构造及其算法 1) 构造哈夫曼树的方法 对于已知的一组叶子的权值1,2,n : (1) 首先把n个叶子结点看做n棵树（有一个结点的二叉树）, 把它们看做一个森林。 (2) 在森林中把权值最小和次小的两棵树合并成一棵树, 该树根结点的权值是两棵子树权值之和。这时森林中还有n-1棵树。 (3) 重复第(2)步直到森林中只有一棵为止。 此树就是哈夫曼树。 现给一组(n=4)具体的权值2, 4, 5, 8, 图 6.22是构造哈夫曼树的具体过程。 2) 哈夫曼算法实现 讨论算法实现需选择合适的存储结构, 这里选用的是顺序存储结构。 因为哈夫曼树中没有度为1的结点。 由二叉树性质可知n0

57、 n2 1, 而现在总结点数为n0 n2, 也即2 n0 1, 叶子数n0若用n表示则二叉树结点总数为2n1。 向量的大小就定义为2n1。假设n10, 存储结构如下: struct nodeh int data; /*权值域*/ int lch, rch; /*左、 右孩子结点在数组中的下标*/ int tag; /* tag=0 结点独立; tag=1 结点已并入树中*/ struct nodeh r; 首先需将叶子权值输入r向量, lch, rch, tag域全置零, 如果用前边的一组数值2, 4, 5, 8初始化向量r, 见图6.23(a)。 然后执行算法, 可得出如图6.23(b)所示

58、的结果。设t为指向哈夫曼树的根结点（在此是数组元素）的指针，算法如算法6.20。 算法 6.20 int huffmah (struct node r20) scanf(nd, n); /* n为叶子结点的个数 */ for(j=1; j=n; j+) scanf(d, rj.data); rj.tag0; rj.lch0; rj.rch0; i0; while (in-1) /* 合并n-1次 */ x1=0; m1 =32767; /* m1是最小值单元, x1为下标号 */ x2 =0; m2 =32767; /* m2为次小值单元, x2为下标号 */ for(j=1; j=n+i;

59、j+) if (rj.datam1)&(rj.tag=0)） m2 = m1; x2 = x1; m1 =rj.data; x1 =j; else if (rj.data=90)、 良(80=x90)、中(70=x80)、 及格(60=x70)、 不及格(x60) 5 个等级。若不考虑学生考试分数的分布概率, 程序判定过程很容易写成图6.23(a)所示的方法。 我们知道, 一般来讲学生考分大多分布在7080分之间, 从图6.23(a)可看出这种情况的x值要比较2至3 次才能确定等级。而学生中考试不及格的人数很少, x值比较一次即可定等级。能否使出现次数多的在7080分之间的x值比较次数减少些,

60、 而使很少出现的低于60分的x值比较次数多一些, 以便提高程序的运行效率呢？ 假设学生成绩对于不及格、及格、中等、良好和优秀的分布概率分别为5, 15, 40, 30, 10, 以它们为叶子的权值来构造哈夫曼树, 如图6.23(b)所示。 此时带权路径长最短, 其值为205。 它可以使大部分的分数值经过较少的比较次数得到相应的等级。但是, 事情往往不是绝对的, 此时每个判断框内的条件较为复杂, 比较两次, 反而降低运行效率。所以我们采用折衷作法, 调整后得图6.23(c)判定树。它更加切合实际。 (2) 用于通信编码。 在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短, 可以对电文中