1、第第6章章 树和二叉树树和二叉树6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树遍历二叉树6.4 线索二叉树线索二叉树6.5 树和森林树和森林6.6 哈夫曼树哈夫曼树教学目的、要求教学目的、要求l1领会树和二叉树的类型定义，理解树和二叉树的结构差别。领会树和二叉树的类型定义，理解树和二叉树的结构差别。l2熟记二叉树的主要特性，并掌握它们的证明方法。熟记二叉树的主要特性，并掌握它们的证明方法。l3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。的其它操作。l4理解二叉树的线索化过
2、程以及在中序线索化树上找给定结点的前驱和理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。后继的方法。l5熟练掌握二叉树和树的各种存储结构及其建立的算法。熟练掌握二叉树和树的各种存储结构及其建立的算法。l6学会编写实现树的各种操作的算法。学会编写实现树的各种操作的算法。l7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。6.1 树的定义和基本术语树的定义和基本术语6.1.1树的定义树的定义l树是由树是由n（n0）个结点组成的有限集合。若）个结点组成的有限集合。若n=0，称为空树；若称为空树；若n0，则：，则：有一个特
3、定的称为根（root）的结点。它只有直接后继，但没有直接前驱；除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。l由此可知，树的定义是一个递归的定义，即树的定由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。义中又用到了树的概念。树的结构参见下图：树的结构参见下图：图6.1树的结构l在图在图6.1(c)6.1(c)中，树的根结点为中，树的根结点为A A，该树还可以分为三个互不相交子集，该树还可以分为三个互不相交子集T T
4、0 0，T T1 1，T T2 2，其中，其中T T0 0=B=B，E E，F F，J J，K K，LL，T T1 1=C=C，GG，T T2 2=D=D，H H，I I，MM，其中的其中的T T0 0，T T1 1，T T2 2都是树，称为图都是树，称为图6 6.1(C)1(C)中树的子树，而中树的子树，而T T0 0，T T1 1，T T2 2又可又可以分解成若干棵不相交子树。如以分解成若干棵不相交子树。如T T0 0可以分解成可以分解成T T0000，T T0101两个不相交子集，两个不相交子集，T T0000=E=E，J J，K K，LL，T T0101=F=F，而，而T T0000又
5、可以分为三个不相交子集又可以分为三个不相交子集T T000000，T T001001，T T002002，其中，其中，T T000000=J=J，T T001001=K=K，T T002002=L=L。l树的抽象数据类型定义见教材树的抽象数据类型定义见教材P118-1196.1.2 基本术语基本术语l1.结点结点l指树中的一个数据元素，一般用一个字母表示。指树中的一个数据元素，一般用一个字母表示。l2.度度l一个结点包含子树的数目，称为该结点的度。一个结点包含子树的数目，称为该结点的度。l3.树叶（叶子）树叶（叶子）l度为度为0的结点，称为叶子结点或树叶，也叫终端结点。的结点，称为叶子结点或树
6、叶，也叫终端结点。l4.孩子结点孩子结点l若结点若结点X有子树，则子树的根结点为有子树，则子树的根结点为X的孩子结点，也称的孩子结点，也称为孩子，儿子，子女等。如图为孩子，儿子，子女等。如图6.1（c）中）中A的孩子为的孩子为B，C，D。l5.双亲结点双亲结点l若结点若结点X有子女有子女Y，则，则X为为Y的双亲结点。的双亲结点。l6.祖先结点祖先结点l从根结点到该结点所经过分枝上的所有结点为该结点的从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图祖先，如图6-1（c）中）中M的祖先有的祖先有A，D，H。l7.子孙结点子孙结点l某一结点的子女及子女的子女都为该结点子孙。某一结点的子女及
7、子女的子女都为该结点子孙。l8.兄弟结点兄弟结点l具有同一个双亲的结点，称为兄弟结点。具有同一个双亲的结点，称为兄弟结点。l9.分枝结点分枝结点l除叶子结点外的所有结点，为分枝结点，也叫非终端结除叶子结点外的所有结点，为分枝结点，也叫非终端结点。点。l10.层数层数l根结点的层数为根结点的层数为1，其它结点的层数为从根结点到该结，其它结点的层数为从根结点到该结点所经过的分支数目再加点所经过的分支数目再加1。l11.树的深度（高度）树的深度（高度）l树中结点所处的最大层数称为树的高度，如空树的高度树中结点所处的最大层数称为树的高度，如空树的高度为为0，只有一个根结点的树高度为，只有一个根结点的树
8、高度为1。l12.树的度树的度l树中结点度的最大值称为树的度。树中结点度的最大值称为树的度。l13.有序树有序树l若一棵树中所有子树从左到右的排序是有顺序的，不能若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。颠倒次序。称该树为有序树。l14.无序树无序树l若一棵树中所有子树的次序无关紧要，则称为无序树。若一棵树中所有子树的次序无关紧要，则称为无序树。l15森林森林l若干棵互不相交的树组成的集合为森林。一棵树可以看若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。成是一个特殊的森林。6.1.3 树的表示树的表示1.树形结构表示法树形结构表示法2.凹入
9、法表示法凹入法表示法图图6.1（c）的树的凹入法表示）的树的凹入法表示3.嵌套集合表示法嵌套集合表示法图图6.1（c）的嵌套集合表示）的嵌套集合表示4.广义表表示法广义表表示法l对图对图6-1（c）的树结构，广义表表示法可表示为：）的树结构，广义表表示法可表示为：（A（B（E（J，K，L），），F），），C（G），），D（H（M），），I）6.1.4 树的性质树的性质l性质性质1 树中的结点数等于所有结点的度加树中的结点数等于所有结点的度加1。l证明：根据树的定义，在一棵树中，除根结证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，点以外，每个结点有且仅有一个直接前驱
10、，也就是说，每个结点与指向它的一个分支一也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结直接前驱，因此，树中的结点数等于所有结点的度数加点的度数加1。l性质性质2 度为度为k的树中第的树中第i层上最多有层上最多有ki-1个结点个结点（i1）。）。l下面用数学归纳法证明：下面用数学归纳法证明：l对于对于i=1，显然成立，假设对于，显然成立，假设对于i-1层，上述条层，上述条件成立，即第件成立，即第i-1层最多有层最多有
11、ki-2个结点，个结点，l对于第对于第i层，结点数最多为第层，结点数最多为第i-1层结点数的层结点数的k倍（因为度为倍（因为度为k），故第），故第i层的结点数为层的结点数为ki-2*k=ki-1。l性质性质3 深度为深度为h的的 k叉树最多有叉树最多有 个结点。个结点。l证明：证明：l由性质由性质2可知，若每一层的结点数最多，可知，若每一层的结点数最多，则整个则整个k叉树结点数最多，共有叉树结点数最多，共有l ll当一棵当一棵K叉树上的结点数达到叉树上的结点数达到 时，称为时，称为满满K叉树。叉树。11hKK1011111hhihiKKKKKK11hKKl性质性质4 具有具有n个结点的个结点的
12、k叉树的最小深度叉树的最小深度为为 。（表示取不小于表示取不小于x的最小整数）的最小整数）l证明：设具有证明：设具有n个结点的个结点的k叉树的深度为叉树的深度为h，在该，在该树的前面树的前面h-1层都是满的，即每一层的结点数等层都是满的，即每一层的结点数等于于ki-1个个(1ih-1)，第，第h层（即最后一层）的结点层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的数可能满，也可能不满，这时，该树具有最小的深度。深度。l由性质由性质3知道，结点数知道，结点数n应满足下面条件：应满足下面条件：log11Kn KX11111hhKKnKKl通过转换为：通过转换为：kh-1n(k-1)
13、+1kh，再取以，再取以k为为底的对数后，可以得到：底的对数后，可以得到：l h-1logk(n(k-1)+1)hl即有：即有：logk(n(k-1)+1)hn，则结点，则结点i无左孩子，否则无左孩子，否则i的左孩子为的左孩子为2i。即满。即满足足2in的结点为叶子结点；的结点为叶子结点；l若若2i+1n，则结点，则结点i无右孩子，否则无右孩子，否则i的右孩子为的右孩子为2i+1；l若结点若结点i为奇数且不等于为奇数且不等于1，则它的左兄弟为，则它的左兄弟为i-1；l若结点若结点i为偶数且不等于为偶数且不等于n，它的右兄弟为，它的右兄弟为i+1；l结点结点i所在层数所在层数(层次层次)为为 ；
14、2log1n log1nn/2i 2log1i 6.2.3 二叉树的存贮结构二叉树的存贮结构1.顺序存贮结构顺序存贮结构l按二叉树的结点按二叉树的结点自上而下、从左至右自上而下、从左至右编号，编号，用一组连续的存储单元存储。用一组连续的存储单元存储。l若该二叉树为非完全二叉树，则必须将相应若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树位置空出来，使存放的结果符合完全二叉树形状。形状。图6.7 二叉树的顺序存储对于一棵二叉树，若采用顺序存贮时，当它为完全二叉树时，比较方便,若为非完全二叉树，将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支，设高度为K，则
15、需占用2K-1个存贮单元，而实际只有k个元素，实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。2.二叉链表存贮结构二叉链表存贮结构 二叉链表表示二叉链表表示l将一个结点分成三部分，一部分存放结点本身信息，将一个结点分成三部分，一部分存放结点本身信息，另外两部分为指针，分别存放左、右孩子的地址。另外两部分为指针，分别存放左、右孩子的地址。l注：如果需要倒查某结点的双亲，可以再增加一个注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链双亲域（直接前趋）指针，将二叉链表变成三叉链表。表。lchilddatarchildl对于图对于图6.7
16、所示二叉树，用二叉链表形式描述。所示二叉树，用二叉链表形式描述。图6.8 二叉树的二叉链表表示 二叉链表的数据类型二叉链表的数据类型bitree.hl/二叉链表定义二叉链表定义l#include lusing namespace std;ltypedef char TElemType;lstruct BiTNodelTElemType data;lBiTNode*lchild,*rchild;l;ltypedef BiTNode*BiTree;lvoid initBiTree(BiTree&T);lvoid createBiTree(BiTree&T);l/递归前序遍历递归前序遍历lvoid
17、preOrderTraverse(BiTree T,void(*visit)(TElemType);l/非递归前序遍历非递归前序遍历lvoid preOrderTraverse1(BiTree T,void(*visit)(TElemType);l/递归中序遍历递归中序遍历l void inOrderTraverse(BiTree T,void(*visit)(TElemType);l/递归后序遍历递归后序遍历lvoid postOrderTraverse(BiTree T,void(*visit)(TElemType);二叉链表的建立二叉链表的建立l为了后面遍历二叉树方便，先介绍建立二叉为了
18、后面遍历二叉树方便，先介绍建立二叉链表的算法（假设链表的算法（假设ElemType 为为char型）。型）。l/按先序次序输入二叉树中结点的值（按先序次序输入二叉树中结点的值（#表示空格），表示空格），l/构造二叉链表表示的二叉树构造二叉链表表示的二叉树T。lvoid createBiTree(BiTree&T)lTElemType ch;lcinch;lif(ch=#)/空空lT=NULL;lelselT=new BiTNode;lif(!T)lexit(1);lT-data=ch;/生成根结点生成根结点lcreateBiTree(T-lchild);/构造左子树构造左子树lcreateBi
19、Tree(T-rchild);/构造右子树构造右子树ll6.3 遍历二叉树遍历二叉树l遍历是树结构插入、删除、修改、查找和排序运算遍历是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。的前提，是二叉树一切运算的基础和核心。l所谓所谓遍历二叉树遍历二叉树，就是遵从某种次序，访问二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。中的所有结点，使得每个结点仅被访问一次。l这里提到的这里提到的访问访问是指对结点施行某种操作，操作是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要可以是输出结点信息，修改结点的数据值等，但要求这种
20、访问不破坏它原来的数据结构。在本书中，求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息我们规定访问是输出结点信息data，且以二叉链表，且以二叉链表作为二叉树的存贮结构。作为二叉树的存贮结构。l由于二叉树是一种非线性结构，每个结点可能有一由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定个以上的直接后继，因此，必须规定遍历的规则遍历的规则，并按此规则遍历二叉树，最后得到二叉树所有结点并按此规则遍历二叉树，最后得到二叉树所有结点的一个线性序列。的一个线性序列。l令令L、R、D分别代表二叉树的左子树、右子树、根分别代表二叉树的左子树、右子树、根结点，
21、则遍历二叉树有结点，则遍历二叉树有6种规则：种规则：DLR、DRL、LDR、LRD、RDL、RKD。若。若规定二叉树中必须先规定二叉树中必须先左后右左后右(左右顺序不能颠倒左右顺序不能颠倒)，则只有，则只有DLR、LDR、LRD三种遍历规则。三种遍历规则。DLR称为前根遍历称为前根遍历(或前序遍历、或前序遍历、先序遍历、先根遍历先序遍历、先根遍历)，LDR称为中根遍历称为中根遍历(或中序或中序遍历遍历)，LRD称为后根遍历称为后根遍历(或后序遍历或后序遍历)。6.3.1 前序遍历前序遍历l所谓前序遍历，就是根结点最先遍历，其次所谓前序遍历，就是根结点最先遍历，其次左子树，最后右子树。左子树，最
22、后右子树。1.递归遍历递归遍历l前序遍历二叉树的递归遍历算法描述为：前序遍历二叉树的递归遍历算法描述为：l若二叉树为空，则算法结束；若二叉树为空，则算法结束；l否则否则l输出根结点；输出根结点；l前根遍历左子树前根遍历左子树;l前根遍历右子树。前根遍历右子树。l/先序递归遍历先序递归遍历T，对每个结点调用函数，对每个结点调用函数Visit一次且仅一次一次且仅一次lvoid preOrderTraverse(BiTree T,void(*visit)(TElemType)lif(T)/T不空不空lvisit(T-data);/先访问根结点先访问根结点lpreOrderTraverse(T-lch
23、ild,visit);/再先序遍历左子树再先序遍历左子树lpreOrderTraverse(T-rchild,visit);/最后先序遍历右子树最后先序遍历右子树ll2.非递归遍历非递归遍历l利用一个一维数组作栈，来存贮二叉链表中利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：结点，算法思想为：l从二叉树根结点开始，沿左子树一直走到末从二叉树根结点开始，沿左子树一直走到末端端(左孩子为空左孩子为空)为止，在走的过程中，访问所为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向为空时，从栈顶退出某结点
24、，并将指针指向该结点的右孩子。如此重复，直到栈为空或该结点的右孩子。如此重复，直到栈为空或指针为空止。指针为空止。l/前序遍历二叉树前序遍历二叉树T的非递归算法的非递归算法(利用栈利用栈)，对每个数据元素调用函数，对每个数据元素调用函数Visitlvoid preOrderTraverse1(BiTree T,void(*visit)(TElemType)lBiTree s100;lint top=0;/top为栈顶指针为栈顶指针lwhile(T!=NULL)|(top0)lwhile(T!=NULL)lvisit(T-data);l stop+=T;lT=T-lchild;llT=s-top
25、;lT=T-rchild;ll6.3.2 中序遍历中序遍历l所谓中序遍历，就是根在中间，先左子树，所谓中序遍历，就是根在中间，先左子树，然后根结点，最后右子树。然后根结点，最后右子树。l中序遍历二叉树的递归遍历算法描述为：中序遍历二叉树的递归遍历算法描述为：l若二叉树为空，则算法结束；若二叉树为空，则算法结束；l否则否则l中根遍历左子树中根遍历左子树;l输出根结点输出根结点;l中根遍历右子树。中根遍历右子树。l/中序递归遍历中序递归遍历T,对每个结点调用函数对每个结点调用函数Visit一次且仅一次一次且仅一次lvoid inOrderTraverse(BiTree T,void(*visit)
26、(TElemType)lif(T)linOrderTraverse(T-lchild,visit);/先中序遍历左子树先中序遍历左子树lvisit(T-data);/再访问根结点再访问根结点linOrderTraverse(T-rchild,visit);/最后中序遍历右子树最后中序遍历右子树ll6.3.3 后序遍历后序遍历l所谓后序遍历，就是根在最后，即先左子树，所谓后序遍历，就是根在最后，即先左子树，然后右子树，最后根结点。然后右子树，最后根结点。l后序遍历二叉树的递归遍历算法描述为：后序遍历二叉树的递归遍历算法描述为：l若二叉树为空，则算法结束；若二叉树为空，则算法结束；l否则否则l后根
27、遍历左子树后根遍历左子树:l后根遍历历子树后根遍历历子树;l访问根结点。访问根结点。l/后序递归遍历后序递归遍历T，对每个结点调用函数，对每个结点调用函数Visit一次且仅一次一次且仅一次lvoid postOrderTraverse(BiTree T,void(*visit)(TElemType)lif(T)linOrderTraverse(T-lchild,visit);/后序遍历左子树后序遍历左子树linOrderTraverse(T-rchild,visit);/再后序遍历右子树再后序遍历右子树lvisit(T-data);/最后访问根结点最后访问根结点ll6.3.4 按层次遍历按层次
28、遍历l对于一棵二叉树，若规定遍历顺序为从上到对于一棵二叉树，若规定遍历顺序为从上到下下(上层遍历完才进入下层上层遍历完才进入下层)，从左到右，从左到右(同一同一层从左到右进行，这样的遍历称为按层次遍层从左到右进行，这样的遍历称为按层次遍历。历。l下面用一个一维数组来模拟队列，实现二叉下面用一个一维数组来模拟队列，实现二叉树的层次遍历。树的层次遍历。l/层序遍历层序遍历T(利用队列利用队列),对每个结点调用函数对每个结点调用函数Visit一次且仅一次一次且仅一次lvoid levelOrderTraverse(BiTree T,void(*visit)(TElemType)lBiTree q10
29、0,p;lint f,r;/f,r类似于头尾指针类似于头尾指针lq0=T;lf=0;lr=1;lwhile(fdata);lif(p-lchild!=NULL)lqr+=p-lchild;/入队入队lif(p-rchild!=NULL)lqr+=p-rchild;/入队入队ll6.4 线索二叉树线索二叉树6.4.1 线索的概念线索的概念l通过前面介绍的二叉树可知，遍历二叉树实通过前面介绍的二叉树可知，遍历二叉树实际上就是将树中所有结点排成一个际上就是将树中所有结点排成一个线性序列线性序列（即非线性结构线性化），在这样的线性序（即非线性结构线性化），在这样的线性序列中，很容易求得某个结点在某种遍
30、历下的列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。点的直接前驱和直接后继记录下来。l为了做到这一点，可以在原来的二叉链表结为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低单元，
31、存贮空间的利用率相当低(一个结点中一个结点中有有4个指针，个指针，1个指左孩子，个指左孩子，1个指右孩子，个指右孩子，1个指前驱，个指前驱，1个指后继个指后继)，而原来的左、右孩，而原来的左、右孩子域有许多空指针又没有利用起来（在有子域有许多空指针又没有利用起来（在有n个个结点的二叉链表中必定存在结点的二叉链表中必定存在n+1个空链域）。个空链域）。l为了不浪费存存贮空间，我们利用原有的孩为了不浪费存存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样子指针为空时来存放直接前驱和后继，这样的指针称为的指针称为线索线索，加线索的过程称为线索，加线索的过程称为线索化，加了线索的二叉树，
32、称为化，加了线索的二叉树，称为线索二叉树线索二叉树，对应的二叉链表称为对应的二叉链表称为线索二叉链表线索二叉链表。l在线索二叉树中，由于有了线索，无需遍历在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢接前驱或直接后继信息呢?为此，在二叉链表为此，在二叉链表结点中，还必须增加两个标志域结点中，还必须增加两个标志域ltag、rtag。lltag和和rtag定义
33、如下：定义如下：01lchildltaglchild域指向结点的左孩子域指向结点在某种遍历下的直接前驱01rchildrtagrchild域指向结点的左孩子域指向结点在某种遍历下的直接后继这样，二叉链表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下：lchildltagdatartagrchildl前序序列为：前序序列为：ABCD。图 前序线索l中序序列为：中序序列为：BADC。图 中序线索l后序序列为：后序序列为：BDCA。图 后序线索6.4.3 线索的算法实现线索的算法实现l在此，仅介绍中序线索二叉树的算法实现。在此，仅介绍中序线
34、索二叉树的算法实现。l为方便起见，依照线性表的存储结构，在二叉树的线索链表为方便起见，依照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其上也添加一个头结点，并令其lchild域的指针指向二叉树的域的指针指向二叉树的根结点，其根结点，其rchild域的指针指向中序遍历时访问的最后一个域的指针指向中序遍历时访问的最后一个结点，并令二叉树中序序列中的第一个结点的结点，并令二叉树中序序列中的第一个结点的lchild域指针域指针和最后一个结点的和最后一个结点的rchild域的指针均指向头结点。域的指针均指向头结点。图 中序线索链表（中序序列为：BADC）l由于线索化的实质是将二叉链表中的
35、空指针由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过的过程即为在遍历的过程中修改空指针的过程。程。l为了记下遍历过程中访问结点的先后关系，为了记下遍历过程中访问结点的先后关系，需附设一个指针需附设一个指针pre始终指向刚刚访问过的结始终指向刚刚访问过的结点。点。1.线索链表类型定义线索链表类型定义inthreading.hl#include lusing namespace std;ltypedef char TE
36、lemType;lenum PointerTagLink,Thread;/Link=0:指针，指针，Thread=1:线索线索lstruct BiThrNodelTElemType data;lBiThrNode*lchild,*rchild;lPointerTag ltag,rtag;l;ltypedef BiThrNode*BiThrTree;lvoid createBiThrTree(BiThrTree&T);lvoid preOrderTraverse(BiThrTree T,void(*visit)(TElemType);lBiThrNode*inOrderThreading(BiT
37、hrTree T);lvoid inTraverseThr(BiThrTree T,void(*visit)(TElemType);2.实现实现inthreading.cppl#include inthreading.hl/按先序次序输入二叉树中结点的值（按先序次序输入二叉树中结点的值（#表示空格），构造二叉线索树表示空格），构造二叉线索树Tlvoid createBiThrTree(BiThrTree&T)lTElemType ch;lcinch;lif(ch=#)/空空lT=NULL;lelselT=new BiThrNode;lif(!T)lexit(1);lT-data=ch;/生成根
38、结点生成根结点llcreateBiThrTree(T-lchild);/构造左子树构造左子树lif(T-lchild)/有左孩子有左孩子lT-ltag=Link;lcreateBiThrTree(T-rchild);/构造右子树构造右子树lif(T-rchild)/有右孩子有右孩子lT-rtag=Link;ll/先序递归遍历先序递归遍历T,对每个结点调用函数对每个结点调用函数Visit一次且仅一次一次且仅一次void preOrderTraverse(BiThrTree T,void(*visit)(TElemType)if(T)/T不空不空visit(T-data);/先访问根结点先访问根结
39、点preOrderTraverse(T-lchild,visit);/再先序遍历左子树再先序遍历左子树preOrderTraverse(T-rchild,visit);/最后先序遍历右子树最后先序遍历右子树BiThrTree pre;/全局变量全局变量,始终指向刚刚访问过的结点始终指向刚刚访问过的结点void inThreading(BiThrTree p)/中序遍历进行中序线索化中序遍历进行中序线索化if(p)inThreading(p-lchild);/左子树线索化左子树线索化if(!p-lchild)/没有左孩子没有左孩子p-ltag=Thread;/前驱线索前驱线索p-lchild=p
40、re;/左孩子指针指向前驱左孩子指针指向前驱if(!pre-rchild)/前驱没有右孩子前驱没有右孩子pre-rtag=Thread;/后继线索后继线索pre-rchild=p;/前驱右孩子指针指向后继前驱右孩子指针指向后继(当前结点当前结点p)pre=p;/保持保持pre始终指向刚刚访问过的结点始终指向刚刚访问过的结点inThreading(p-rchild);/右子树线索化右子树线索化l/中序遍历二叉树中序遍历二叉树T,并将其中序线索化并将其中序线索化,lBiThrNode*inOrderThreading(BiThrTree T)lBiThrNode*Thrt=new BiThrNod
41、e;/Thrt指向头结点指向头结点l Thrt-ltag=Link;lThrt-rtag=Thread;lThrt-rchild=Thrt;/右指针回指右指针回指lif(!T)/若二叉树空，则左指针回指若二叉树空，则左指针回指lThrt-lchild=Thrt;lelselThrt-lchild=T;lpre=Thrt;linThreading(T);/中序遍历进行中序线索化中序遍历进行中序线索化lpre-rtag=Thread;/最后一个结点线索化最后一个结点线索化lpre-rchild=Thrt;lThrt-rchild=pre;llreturn Thrt;ll/中序遍历二叉线索树中序遍历
42、二叉线索树T(头结点头结点)的非递归算法的非递归算法lvoid inTraverseThr(BiThrTree T,void(*visit)(TElemType)lBiThrTree p;lp=T-lchild;/p指向根结点指向根结点lwhile(p!=T)/空树或遍历结束时空树或遍历结束时,p=Tlwhile(p-ltag=Link)lp=p-lchild;lvisit(p-data);/访问左子树为空的结点访问左子树为空的结点lwhile(p-rtag=Thread&p-rchild!=T)lp=p-rchild;lvisit(p-data);/访问后继结点访问后继结点llp=p-rch
43、ild;ll6.5 树和森林树和森林6.5.1 树的存储结构树的存储结构1.双亲表示法双亲表示法l它是以一组连续的存储单元来存放树中的结点，每它是以一组连续的存储单元来存放树中的结点，每个结点有两个域：一个是个结点有两个域：一个是data域，存放结点信息，域，存放结点信息，另一个是另一个是parent域，用来存放双亲的位置域，用来存放双亲的位置(指针指针)。树的双亲表示法2.孩子表示法孩子表示法l将一个结点所有孩子链接成一个单链表形，而树中将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结
44、点用一个数组来描述。一个表头结点，所有表头结点用一个数组来描述。树的孩子表示法3.双亲孩子表示法双亲孩子表示法l将第将第1、2两种方法结合起来，则得到双亲孩两种方法结合起来，则得到双亲孩子表示法。子表示法。双亲孩子表示法4.孩子兄弟表示法孩子兄弟表示法l类似于二叉链表，但第一根链指向第一个孩子，第类似于二叉链表，但第一根链指向第一个孩子，第二根链指向下一个兄弟。二根链指向下一个兄弟。孩子兄弟表示法6.5.2 树、森林和二叉树的转换树、森林和二叉树的转换1.树转换成二叉树（孩子树转换成二叉树（孩子-兄弟表示法）兄弟表示法）l可以分为三步：可以分为三步：l加线加线l将树中同一结点的兄弟相连将树中同
45、一结点的兄弟相连;l抹线抹线l保留结点的最左孩子连线，删除其它孩子保留结点的最左孩子连线，删除其它孩子连线；连线；l旋转旋转l将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转45度角。度角。l讨论：二叉树怎样还原为树？讨论：二叉树怎样还原为树？l要点：逆操作，把所有右孩子变为兄弟！要点：逆操作，把所有右孩子变为兄弟！树转换成二叉树2.森林转换成二叉树森林转换成二叉树l将森林中每一棵树分别转换成二叉树；将森林中每一棵树分别转换成二叉树；l合并：使第合并：使第n棵树接入到第棵树接入到第n-1棵的右边并棵的右边并成为它的右子树，第成为它的右子树，第 n-1 棵二叉树接入到第棵二叉树接入到第n
46、-2 棵的右边并成为它的右子树，棵的右边并成为它的右子树，第，第2棵棵二叉树接入到第二叉树接入到第1棵的右边并成为它的右子树，棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。直到最后剩下一棵二叉树为止。森林转换成二叉树3.二叉树还原成树或森林二叉树还原成树或森林l右链断开右链断开l将二叉树的根结点的右链及右链的右链等将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。全部断开，得到若干棵无右子树的二叉树。l二叉树还原成树二叉树还原成树l将中得到的每一棵二叉树都还原成树将中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反）。（与树转换成二叉树的步骤刚好相反
47、）。二叉树还原成森林的过程6.5.3 树和森林的遍历树和森林的遍历l在树和森林中，一个结点可能有两棵以上的在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，子树，所以不宜讨论它们的中序遍历，即树即树和森林和森林只有先序遍历和后序遍历只有先序遍历和后序遍历。1.先序遍历先序遍历l 树的先序遍历树的先序遍历l若树非空，则先访问根结点，然后依次先若树非空，则先访问根结点，然后依次先序遍历各子树。序遍历各子树。l 森林的先序遍历森林的先序遍历l若森林非空，则先访问森林中第一棵树的若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着根结点，再先序遍历第一棵树各
48、子树，接着先序遍历第二棵树、第三棵树、先序遍历第二棵树、第三棵树、直到最、直到最后一棵树。后一棵树。2.后序遍历后序遍历l 树的后序遍历树的后序遍历l若树非空，则依次后序遍历各子树，最后访问根若树非空，则依次后序遍历各子树，最后访问根结点。结点。l 森林的后序遍历森林的后序遍历l按顺序后序遍历森林中的每一棵树。按顺序后序遍历森林中的每一棵树。l另外，请注意，树和森林的先序遍历等价于它转换另外，请注意，树和森林的先序遍历等价于它转换成的二叉树的先序遍历，树和森林的后序遍历等价成的二叉树的先序遍历，树和森林的后序遍历等价于它转换成的二叉树的中序遍历。于它转换成的二叉树的中序遍历。6.6 哈夫曼树哈
49、夫曼树6.6.1 基本术语基本术语l1.路径和路径长度路径和路径长度l在一棵树中，从一个结点往下可以达到的孩子或在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为子孙结点之间的通路，称为路径路径。通路中分支的数。通路中分支的数目称为目称为路径长度路径长度。l若规定根结点的层数为若规定根结点的层数为1，则从根结点到第，则从根结点到第L层层结点的路径长度为结点的路径长度为L-1。l2.结点的权及带权路径长度结点的权及带权路径长度l若将树中结点赋给一个有着某种含义的数值，则若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的这个数值称为该结点的权权。l结点的带权路径长度为：
50、从根结点到该结点之间结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。的路径长度与该结点的权的乘积。l3.树的带权路径长度树的带权路径长度l树的树的带权路径长度带权路径长度规定为所有叶子结点的规定为所有叶子结点的带权路径长度之和，记为带权路径长度之和，记为l其中其中n 为叶子结点数目，为叶子结点数目，wk为第为第k个叶子结点个叶子结点的权值，的权值，lk为第为第k个叶子结点的路径长度。个叶子结点的路径长度。1nk kkWPLw ll4.哈夫曼树哈夫曼树l在一棵二叉树中，若带权路径长度达到最小，称这样的在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为二叉树为最优二叉
