第6章 树 数据结构（C++描述）
目录 6.1 树的基本概念 6.2 二叉树 6.3遍历二叉树 6.4线索二叉树 ６.５树和森林 6.6 哈夫曼树 退出
6.1 树的基本概念 6.1.1 树的定义 1．树的定义 树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则： （1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。 树的结构参见图6-1。
在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0={B，E，F，J，K，L}，T1={C，G}，T2={D，H，I，M}，其中的T0，T1，T2都是树，称为图6-1（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00={E，J，K，L}，T01={F}，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。
2．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k={ki∣1≤i≤n;n≥0,kielemtype} R={r} 其中，n为树中结点个数，若 n=0，则为一棵空树， n> 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。
例如，对图6-1(c )的树结构,可以二元组表示为： K={A，B，C，D，E，F，G，H，I，J，K，L，M} R={r} r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)} 3．树的基本运算 树的基本运算可以定义如下几种： (1) inittree(&T) 初始化树T。 (2) root(T) 求树T的根结点。
(3) parent(T,x) 求树T中，值为x的结点的双亲。 (4) child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T。
6.1.2 基本术语 1.结点 指树中的一个数据元素，一般用一个字母表示。 2.度 一个结点包含子树的数目，称为该结点的度。 3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。 4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。
5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。 6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D ，H 。 7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.兄弟结点 具有同一个双亲的结点，称为兄弟结点。
9.分枝结点 除叶子结点外的所有结点，为分枝结点，也叫非终端结点。 10．层数 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。 11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。 12.树的度 树中结点度的最大值称为树的度。
13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。 15．森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。
6.1.3 树的表示 1．树形结构表示法 具体参 见图6-1 。
2. 凹入法表示法 具体参见图6-3 。
3. 嵌套集合表示法 具体参 见图6-4 。
4.广义表表示法 对图6-1（c）的树结构，广义表表示法可表示为： （A（B（E（J，K，L），F），C（G），D（H（M），I））） 6.1.4 树的性质 性质1 树中的结点数等于所有结点的度加1。 证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。
性质 2 度为k的树中第i层上最多有ki-1个结点（i≥1）。 下面用数学归纳法证明： 对于i=1，显然成立，假设对于i-1层，上述条件成立，即第i-1层最多有ki-2个结点， 对于第i层，结点数最多为第i-1层结点数的k倍（因为度为k），故第i层的结点数为ki-2*k= ki-1。 性质3 深度为h的 k叉树最多有 个结点。 证明：由性质2可知，若每一层的结点数最多，则整个k叉树结点数最多，共有 =k0+k1+…+kh-1= 。 当一棵K叉树上的结点数达到 时，称为满K叉树。
性质4 具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。 （请注意，x 表示取不小于x的最小整数，或叫做对x上取整。） 证明：设具有n个结点的k叉树的深度为h，即在该树的前面h-1层都是满的，即每一层的结点数等于ki-1个(1≤i≤h-1)，第h层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的深度。由性质3知道，结点数n应满足下面条件： <n≤ ，通过转换为：kh-1<n(k-1)+1≤kh，再取以k为底的对数后，可以得到： h-1<logk(n(k-1)+1)≤h，即有：logk(n(k-1)+1)≤h<logk(n(k-1)+1)+1，而h只能取整数，所以，该k叉树的最小深度为h=logk(n(k-1)+1) 。
6.2 二叉树 6.2.1 二叉树的定义 1．二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图6-5 。
2．二叉树的基本运算 （1）inittree(&T) 二叉树的初始化。 （2）root(T) 求二叉树的根结点。 （3）parent(T,x) 求二叉树T中值为x的结点的双亲。 （4）lchild(T,x) 求二叉树T中值为x的结点的左孩子。
(5) rchild(T,x) 求二叉树T中值为x的结点的右孩子。 (6) lbrother(T,x) 求二叉树T中值为x的结点的左兄弟。 (7) rbrother(T,x) 求二叉树T中值为x的结点的右兄弟。 (8) traverse(T) 遍历二叉树T。
(9) createtree(&T) 建立一棵二叉树T。 (10) addlchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。 (11) addrchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。 (12) dellchild(&T,x) 在二叉树T中，删除值为x 的结点的左孩子。 (13) delrchild(&t,x) 在二叉树T中，删除值为x 的结点的右孩子。
6.2.2 二叉树的性质 性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k>0）。 可以用数学归纳法证明之。 性质2 深度（高度）为k的二叉树最大结点数为2k-1（k>0）。 证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+…+2k-1=2k-1。
性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2 ，而一棵二叉树中，除根结点外所有都为孩子 结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。 为继续给出二叉树的其它性质，先定义两种特殊的二叉树。
满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。 从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。 完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~ n的结点一一对应，则称这棵二叉树为完全二叉树。 从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。
从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图6-6所示。
性质4 具有n个结点的完全二叉树高度为log2(n)+1 或 log2（n+1） 。 (注意x表示取不大于x的最大整数，也叫做对x下取整，x表示取不小于x的最小整数，也叫做对x上取整。) 证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉具有k层，第k层至少至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2k-1 –1） +1 ≤n ≤（2k-1-1）+2k-1，即有 2k-1≤n≤2k-1。由式子后半部分可知, n≤2k-1…① 由式子前半部分可知 2k-1≤n…② 由①有 n+1≤2k ，同时取对数得： log2(n+1)≤k 故 k≥log2(n+1),即 k=log2(n+1)。即得到第二个结论。 由②有2k-1≤n,同时取对数得：k≤log2n+1即 k=log2 n+1,即第一个结论成立,证毕。
性质5如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，…，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简称编号为j的结点为 j(1≤j≤n)，则有如下结论成立： （1）若 j=1，则结点j为根结点，无双亲，否则j的双亲为 j/2； （2）若2j≤n，则结点j的左子女为2j ,否则无左子女。即满足2j>n的结点为叶子结点； （3）若2j+1≤n，则结点j的右子女为2j+1，否则无右子女； （4）若结点j序号为奇数且不等于1，则它的左兄弟为j-1； （5）若结点j序号为偶数且不等于n，它的右兄弟为j+1； （6） 结点j所在层数(层次)为log2j+1；
6.2.3 二叉树的存贮结构 1．顺序存贮结构 将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图6-7给出了顺序存贮形式。
对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支,设高度为K,则需占用2K-1个存贮单元,而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。 2．二叉链表存贮结构 （1）二叉链表表示 将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。 二叉链表中一个结点可描述为:
对于图6-7所示二叉树,用二叉链表形式描述见图6-8。
对于一棵二叉树,若采用二叉链表存贮时,当二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占用较多存贮单元(存放地址的指针)。若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用,被白白浪费掉了,(当然后面介绍的线索可利用它)。 （2）二叉链表的数据类型 二叉链表的数据类型描述如下: struct bitree { elemtype data ; //结点数据类型 bitree *lchild, *rchild;} //定义左、右孩子为指针型
(3)二叉链表的建立 为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设elemtype 为char型）。 假设二叉链表的数据类型描述如刚才所述，为建立二叉链表，用一个一维表数组来模拟队列，存放输入的结点，但是，输入结点时，必须按完全二叉树形式，才能使结点间满足性质5，若为非完全二叉树，则必须给定一些假想结点(虚结点)，使之符合完全二叉树形式。为此，我们在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，输入逗号，最后以一个特殊符号 “#”作为输入的结束,表示建二叉链表已完成。建成的二叉链表可以由根指针root唯一确定。
算法描述如下： #include<iostream.h> typedef char elemtype; struct bitree { elemtype data; bitree *lchild,*rchild;}; bitree *create() { bitree *q[100]; //定义q数组作为队列存放二叉链表中结点，100为最大容量 bitree *s; //二叉链表中的结点 bitree *root ; //二叉链表的根指针 int front=1,rear=0; //定义队列的头、尾指针
char ch; //结点的data域值 root=NULL; cin>>ch; while(ch!='#') //输入值为#号,算法结束 { s=NULL; if(ch!=',') //输入数据不为逗号,表示不为虚结点,否则为虚结点 { s=new bitree; s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; q[rear]=s; //新结点或虚结点进队
if(rear==1) root=s; else { if((s!=NULL)&&(q[front]!=NULL)) { if(rear%2==0) q[front]->lchild=s; //rear为偶数,s为双亲左孩子 else q[front]->rchild=s;} //rear为奇数,s为双亲右孩子 if(rear%2==1) front++; } //出队 cin>>ch;} return root; }
例如，对图6-9所示的二叉树，建立的二叉链表如图6-10所示。
对图6-9(a)所示的二叉树，要用算法建成图6-10所示的二叉树链表，从键盘输入的数据应为：AB,,C,,,,D#↙ 其中#为输入结束，↙为回车符。
6.3遍历二叉树 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。 这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。
由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列。 令L,R,D分别代表二叉树的左子树、右子树、根结点，则遍历二叉树有6种规则：DLR、DRL、LDR、LRD、RDL、RKD。若规定二叉树中必须先左后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD三种遍历规则。DLR称为前根遍历(或前序遍历、先序遍历、先根遍历)，LDR称为中根遍历(或中序遍历)，LRD称为后根遍历(或后序遍历)。
6.3.1前根遍历 所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。 1．递归遍历 前根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束;否则 （1）输出根结点； （2）前根遍历左子树; （3）前根遍历右子树;
算法如下: void preorder(bitree *root) { bitree *p; p=root; if(p!=NULL) {cout<<p->data<<“ ”; preorder(p->lchild); preorder (p->rchild);} }
2．非递归遍历 利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为： 从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。
算法如下： void preorder1(bitree *root) { bitree *p,*s[100]; int top=0; //top为栈顶指针 p=root; while((p!=NULL)||(top>0)) { while(p!=NULL) {cout<<p->data<<" "; s[++top]=p; p=p->lchild; } p=s[top--]; p=p->rchild; }}
6.3.2中根遍历 所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。 1．递归遍历 中根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束；否则 ⑴中根遍历左子树; ⑵输出根结点; ⑶中根遍历右子树。
算法如下: void inorder(biteee *root) { bitree *p; p=root; if (p!=NULL) { inorder(p->lchild); cout<<p->data<<“ ”; inorder(p->rchild); }
2．非递归遍历 同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为： 从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。
算法如下: void inorder1( bitree *root) { bitree *p,*s[100]; //s为一个栈，top为栈顶指针 int top=0; p=root; while((p!=NULL)||(top>0)) { while(p!=NULL) {s[++top]=p;p=p->lchild;} {p=s[top--]; cout<<p->data<<" "; p=p->rchild; } }}
6.3.3 后根遍历 所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。 1．递归遍历 后根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束;否则 （1）后根遍历左子树: （2）后根遍历历子树; （3）访问根结点。
算法如下: void postorder( bitree *root) { bitree *p; p=root; if (p!=NULL) { postorder (p->lchild); postorder (p->rchild); cout<<p->data<<“ ”; }
2.非递归遍历 利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该 结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。
后序遍历二叉树的非递归算法如下： void postorder1( bitree *root) { bitree *p,*s1[100]; //s1栈存放树中结点 int s2[100],top=0,b; //s2栈存放进栈标志 p=root; do { while(p!=NULL) {s1[top]=p;s2[top++]=0; //第一次进栈标志为0 p=p->lchild;} if(top>0) {b=s2[--top]; p=s1[top];
if(b==0) {s1[top]=p;s2[top++]=1; //第二次进栈标志为0 p=p->rchild;} else {cout<<p->data<<" "; p=NULL; } }while(top>0);
例如，可以利用上面介绍的遍历算法，写出如图6-11所示二叉树的三种遍历序列为： 先序遍历序列：ABDGCEFH 中序遍历序列： BGDAECFH 后序遍历序列： GDBEHFCA
另外，在编译原理中，有用二叉 树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图6-12。 图6-12所对应的前缀表达式：-*abc。 图6-12所对应的中缀表达式：a*b-c。 图6-12所对应的后缀表达式：ab*c-。
二叉树所对应的遍历序列可以通过递归算法得到，也可以通过非递归算法得到。但有时要求直接写出序列，故我们可以用图6-13所示得到图6-12的遍历序列。从二叉树的三种递归遍历算法可以知道，三种遍历算法不同之处在于访问根结点和遍历左、右子树的顺序不同，若递归算法中去掉与递归无关的语句——访问根结点，则三个遍历算法完全相同。于是对于二叉树的遍历，可以看成是从根结点出发，往左子树走，若左子树为空，返回，再进入右子树，右子树访问完后，再返回根结点。这样一来每个结点都被访问三次，若将按顺序第一次访问的结点排列起来，则得到该二叉树的先序序列，第二次访问的结点排列起来，则得到该二叉树的中序序列，第三次访问的结点排列起来，则得到该二叉树的后序序列。对于图6-13中， 第一次访问到的结点用△表示,第二次访问到的结点用○表示,第三次访问的结点用□表示,按虚线顺序将所有△排列,则得到先序序列为-*abc,将所有○排列起来则得到中序序列为a*b-c,将所有□排列起来则得到后序序列ab*c-。
6.3.4遍历算法应用举例 例6-5 由二叉树的前序序列和中序序列建立该二叉树 分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：
1.用前序序列的第一个结点作为根结点; 2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树); 3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列; 4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。 假设前序序列为ABDGHCEFI， 中序序列为GDHBAECIF， 则得到的二叉树如下页所示
1。A为根结点 A BDGH CEFI GDHB A ECIF 2. B为左子树的根结点 B DGH GDH B
4。C为右子树的根结点 C E FI E C IF 5。F为右子树的右子树的根结点
例6-6 按层次遍历一棵二叉树 对于一棵二叉树，若规定遍历顺序为从上到下(上层遍历完才进入下层)，从左到右(同一层从左到右进行，这样的遍历称为按层次遍历：例6-5的树的层次遍历序列为：ABCDEFGHI。下面用一个一维数组来模拟队列，实现二叉树的层次遍历。
Void lorder (bitree * t) { bitree *q[maxsize],*p; // maxsize为最大容量 int f,r; // f,r类似于头尾指针 q[1]=t; f=r=1; while (f<=r) { p=q[f]; f++; //出队 cout <<p->data; if(p ->lchild!=NULL) { r++; q[r]=p->1child; } //入队 if (p->rchild!=NULL) { r++; q[r]=p->rchild;} //入队 } }
6.4线索二叉树 6.4.1 线索的概念 通过前面介绍的二叉树可知，遍历二叉树实际上就是将树中所有结点排成一个线性序列(即非线性结构线性化)，在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低(一个结点中有4个指针，1个指左孩子，1个指右孩子，1个指前驱，1个指后继)，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为“线索”，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。
在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域ltag、rtag。 ltag和rtag定义如下： 0 lchild域指向结点的左孩子 ltag= 1 lchild域指向结点在某种遍历下的直 接前驱 0 rchild域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继
这样，二叉链表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下： 2．线索的分类 另外，根据遍历的不同要求，线索二叉树可以分为： （1）前序前驱线索二叉树(只需画出前驱) （2）前序后继线索二叉树(只需画出后继)
（3）前序线索二叉树(前驱和后继都要标出) （4）中序前驱线索二叉树(只需画出前驱) （5）中序后继线索二叉树(只需画出中序后继) （6）中序线索二叉树(中序前驱和后继都要标出) （7）后序前驱线索二叉树(只需画出后序前驱) （8）后序后继线索二叉树(中需画出后序后驱) （9）后序线索二叉树(后前驱和后继都要标出)
6.4.2线索的描述 1．结点数据类型描述 struct Hbitree { elemtype data; int ltag ,rtag; //左、右标志域 Hbitree *lchild, *rchild; } ; 2．线索的画法 在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。
前序序列为：ABCD
中序序列为：BADC
后序序列为：BDCA
6.4.3 线索的算法实现 在此，仅介绍中序线索二叉树的算法实现，设为P为当前结点，pre为p的前驱结点，算法描述如下： void inth (Hbitree *p) //将P所指二叉树中序线索化，调用该函数之前，pre为 Null，而树中所有结点的ltag和rtag都为0。 { if (p!=NULL) { inth (p->lchild); 左子树线索化
if (p->lchild==NULLl) p->ltag=1; if (p->rchild==NULL) p->rtag; if (pre!=NULL) { if(pre->rtag==1) pre->rchild=p; if (p->ltag=1) p->lchild=pre; } pre=p; inth (p->rchild); //右子树线索化
6.4.4 线索二叉树上的运算 1．线索二叉树上的查找 （1）查找指定结点在中序线索二叉树中的的直接后继 若所找结点右标志rtag=1，则右孩子域指向中序后继，否则，中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点（参见图 6-19）。从图6-19中可知，x的后继为xk 。
（2）查找指定结点在中序线索二叉树中的的直接前驱 若所找结点左标志ltag=1，则左孩子域指向中序前驱，否则，中序前驱应为遍历左子树时的最后一个访问结点，即左子树中最右下的结点（参见图 6-20）。从图6-20中可知，x的前驱为xk 。
(3) 查找指定点在前序线索二叉树中的直接后继 前序后继的查找比较方便，若Ｐ无左孩子，右链为后继，否则左孩子为后继。 (4) 查找指定结点在后序线索二叉树中的直接前驱 后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子指前驱，否则右孩子为前驱。 求后序后继和前序前驱都比较麻烦，在此不再作进一步介绍。
2．线索二叉树上的遍历 遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。故后序线索对于遍历没有什么意义。 (1)前序遍历线索二叉树算法 void preorder2 (Hbitree *t) Hbitree *p; { p=t; //找到开始结点 while (p!=NULL) { cout <<p->data; p=preordernext(p); //调查函数找前序后继 }}
(2)中序遍历线索二叉树算法 void inorder2 (Hbitree *t) { Hbitree *p;p=t; if (p!=NULL) { while (p->ltag==0) p=p->lchild; //找开始结点 while (p!=NULL) { cout <<p->data; p= inordernext(p); //调用函数找中序后继 }}}
从上面算法可知，线索二叉树上的遍历较一般二叉树要方便得多。但是这种方便是以增加线索为代价的，增加线索本身要花费大量时间。所以二叉树是以二链表表示，还是以线索二叉链表示，可根据具体问题而定。 3．线索二叉树的扦入和删除 线索二树上的查找、遍历都较一般二叉树方便，但线索二叉树也存在其缺点，就扦入和删除运算而言，线索二叉树比一般二叉树的时间花费大，因为除修改指针外，还要修改相应线索。 线索二叉树的扦入和删除较麻烦，因此本书不再介绍算法
６.５树和森林 ６.５.１ 树的存储结构 1．双亲表示 它是以一组连续的存储单元来存放树中的结点，每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 该结构的具体描述见图6-21。
2．孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述，具体描述参见图6-22
3．双亲孩子表示法 将第1、2两种方法结合起来，则得到双亲孩子表示法，具体参见图6-23。
4 。孩子兄弟表示法 类似于二叉链表，但第一根链指向第一个孩子，第二根链指向下一个兄弟。将图6-21(a)的树用孩子兄弟表示法表示，见图6-24。
6.5.2 树、森林和二叉树的转换 1．树转换成二叉树 可以分为三步： （1） 连线 指相邻兄弟之间连线。 （2） 抹线 指抹掉双亲与除左孩子外其它孩子之间的连线。 （3） 旋转 只需将树作适当的旋转。 具体实现过程见图6-25。
2．森林转换成二叉树 （1） 将森林中每一棵树分别转换成二叉树 这在刚才的树转换成二叉树中已经介绍过。 （2）合并 使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，…，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。
3．二叉树还原成树或森林 (1) 右链断开 将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。 具体操作见图6-27(b)。 （2） 二叉树还原成树 将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反）。 具体操作步骤见图6-27(c)。
6.5.3 树和森林的遍历 在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历， 即树和森林只有先序遍历和后序遍历。 1．先序遍历 （1）树的先序遍历 若树非空，则先访问根结点，然后依次先序遍历各子树。 （2）森林的先序遍历 若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、…、直到最后一棵树。
2．后序遍历 （1）树的后序遍历 若树非空，则依次后序遍历各子树，最后访问根结点。 （2）森林的后序遍历 按顺序后序遍历森林中的每一棵树。 另外，请注意，树和森林的先序遍历等价于它转换成的二叉树的先序遍历，树和森林的后序遍历等价于它转换成的二叉树的中序遍历。
6.6 哈夫曼树 6.6.1基本术语 1．路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。 若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 2．结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3．树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl= ，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。 6.6.2 哈夫曼树构造 1．哈夫曼树的定义 在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 例如，给定叶子结点的权分别为1,3,5,7，则可以得到如图6-28所示的不同二叉树。 从图6-28可知，图6-28 (b)的长度最短，图6-28 (c)为较差情形，当然读者还可以自已构造出具有不同的wpl情形来。
2．哈夫曼树的构造 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为： (1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。 下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图6-29所示。 从图6-29可知，n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。
6.6.3哈夫曼树的应用 1．哈夫曼编码 通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。 而哈夫曼编码就是一种不等长的二进制编 码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。
例如，给定权{1,5,7,3}，得到的哈夫曼树及编码见图6-32 (假定权值就代表该字符名字)。
2．哈夫曼译码 在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。