数据结构树和二叉树

第6章树和二叉树学习目的与要求：1.熟练掌握二叉树的结构特性，掌握相应的证明方法；2.熟悉二叉树的各种存储结构的特点及适用范围；3.熟练掌握二叉树各种遍历策略的递归和非递归算法，而且能灵活运用遍历算法实现二叉树的其它操作；4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结树的定义和基本术语1、树的定义树是一种常用的非线性数据结构。它是n(n>=0)个结点的有限集。n=0时，称为空树。在任意一棵非空树中：1）有且仅有一个特定的称为根（Root)的结点；2）当n>1时，其余结点分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。2、树的特点有且只有一个称作根的结点；除根结点以外，其余结点有且只有一个双亲结点。3、树的示例ABCDEFGHIJKLM有子树的树A只有根结点的树子树4、树的基本术语ABCDEFGHIJKLM结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支。结点的度(degree)——结点拥有的子树数。叶子(leaf)——度为0的结点，又称终端结点。孩子(child)——结点子树的根称为该结点的孩子，该结点称为其孩子结点的双亲(parents)兄弟(sibling)——同一双亲的孩子。树的度——一棵树中各结点的度的最大值。结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…深度(depth)——树中结点的最大层次数。森林(forest)——m(m≥0)棵互不相交的树的集合。另：祖先、子孙、堂兄弟、非终端结点、内部结点、无序树、有序树等5、树的基本运算(1)InitTree(&T):构造一棵空树(2)TreeDepth(T):求树的深度(3)Root(T):求树根(4)Parent(T,cur_e):求树T中结点cur_e的双亲(5)LeftChild(T,cur_e):若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。(6)RightSibling(T,cur_e):若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。(7)InsertChild(&T,&p,i,c):插入c为T中p指结点的第i棵子树。(8)DeleteChild(&T,&p,i):删除T中p所指结点的第i棵子树。(9)TraverseTree(T,visit()):按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。……6、树的表示法广义表表示法(a(b(d,e(i,j),f),c(g,h)))基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结二叉树的定义和性质二叉树(binarytree):度不超过2的有序树，是另一种树型结构。二叉树的五种基本形态：(a)空二叉树A(b)仅有根结点的二叉树(c)右子树为空的二叉树A(d)左、右子树均非空的二叉树A(e)左子树为空的二叉树A1、二叉树的定义特点：◆每个结点至多只有两棵子树；◆二叉树的子树有左右之分，其次序不能任意颠倒。2、二叉树的基本运算(1)InitBiTree(&T):构造一棵空二叉树；(2)BiTreeDepth(T):求二叉树的深度；(3)BiTreeEmpty(T):若T为空二叉树，则返回TRUE，否则FALSE；(4)Parent(T,e):

若e是T的非根结点，则返回它的的双亲，否则返回“空”；(5)LeftChild(T,e):返回e的左孩子，若e无左孩子，则返回“空”；(6)RightChild(T,cur_e):

返回e的右孩子，若e无右孩子，则返回“空”；(7)InsertChild(&T,&p,LR,c):

插入c为T中p指结点的由LR的值确定的左（右）子树；(8)DeleteChild(&T,&p,LR):

删除T中p所指结点的由LR的值确定的左（右）子树；(9)PreOrderTraverse(T):先序遍历二叉树T；(10)InOrderTraverse(T):中序遍历二叉树T；(11)PostOrderTraverse(T):后序遍历二叉树T；(12)LevelOrderTraverse(T):层次遍历二叉树T。……3、二叉树的性质:性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。证明性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。证明性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明性质4：具有n个结点的完全二叉树的深度为。证明性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2。(2)如果2i>n，则结点i无左孩子；否则其左孩子是2i。(3)如果2i+1>n，则结点i无右孩子；否则其右孩子是2i+1。证明性质1证明：用归纳法证明之i=1时，只有一个根结点，显然，2i-1=20=1是对的。假设对所有j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，那么，第i-1层至多有2i-2个结点；又二叉树每个结点的度至多为2，第i层上最大结点数是第i-1层的2倍，即2×2i-2=2i-1。故命题得证。性质2证明：由性质1，可得深度为k的二叉树最大结点数是：性质3证明：设n1为二叉树T中度为1的结点数，因为二叉树中所有结点的度均小于或等于2，所以其结点总数为n=n0+n1+n2①

又因为在二叉树中，除根结点外，其余结点都只有一个分支进入。设B为分支总数，则n=B+1。而分支是由度为1和度为2的结点射出，所以B=n1+2n2，于是，n=B+1=n1+2n2+1②由①和②得：n0=n2+1123567两种特殊形态的二叉树满二叉树：一棵深度为k且有2k-1个结点的二叉树完全二叉树：深度为k有n个结点且每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应的二叉树特点：1)叶子结点只可能在最下面两层上;2)任意结点的左右分支下的子孙最大层次0≤l左-l右≤1;3)深度为k的完全二叉树，第i(1≤i≤k-1)层上结点数等于2i-11231145891213671014151231145891267101234567123456性质4证明：假设完全二叉树的深度为k，根据性质2和完全二叉树的定义有2k-1-1<n≤2k-1或2k-1≤n<2k于是k-1≤log2n<k，因为k是整数，所以k=log2n+1。123114589126710性质5证明：先证明（2）和（3），即可推出（1）对于i=1，由完全二叉树的定义，其左孩子是结点2，若2>n，此时结点i无左孩子；结点i的右孩子也只能是结点3，若3>n，此时结点i无右孩子。对于i>1可以分成两种情况：①设第j层的第一个结点的编号为i（由性质2可知i=2j-1），则其左孩子必为j+1的第一个结点，其编号为2j=2(2j-1)=2i，若2i>n，则无左孩子；其右孩子必为第j+1层的第二个结点，其编号为2i+1，若2i+1>n，则无右孩子。②假设第j层上某个结点的编号为i（2j-1≤i<2j-1），且2i+1<n，则其左孩子为2i，右孩子为2i+1；又编号为i+1的结点是编号为i的结点的右兄弟或者堂兄弟，若它有左孩子，则编号必为2i+2=2(i+1)，若它有右孩子，则其编号必为2i+3=2(i+1)+1。基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结二叉树的存储结构二叉树的存储结构有多种，最常用的有两种：顺序存储结构和链表存储结构。该存储结构的特点：操作简单，根据性质5可计算出任一结点的双亲与孩子的存储位置。浪费空间：一个深度为k的单支树需要2k-1个存储空间。1、顺序存储结构

二叉树可以存放在一维数组中，这是一种简单的顺序存储结构。#defineMAX_TREE_SIZE20typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];//1号单元存储根结点SqBiTreebt;123456789101112完全二叉树的存储结构71234500006非完全二叉树的存储结构2、链式存储结构二叉链表的存储表示如下：typedefstructBiNode{TElemTypedata;//数据域structBiNode*lchild,*rchild;//左、右孩子指针}BiNode,*BiTree;容易证明：在含有n个结点的二叉链表中有n+1个空链二叉树的链表结构二叉链表三叉链表线索链表三叉链表的存储表示如下：typedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild,*parent;}BiNode,*BiTree;基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结遍历二叉树遍历二叉树：是指按某种搜索路径访问树中每个结点，使得每个结点访问且只被访问一次。访问：对结点做各种处理，如输出结点信息等遍历二叉树的方法：先（根）序遍历(DLR)、中（根）序遍历(LDR)

后（根）序遍历(LRD)、层次遍历1、先序遍历二叉树先序遍历二叉树的操作定义:若二叉树为空，则空操作；否则1)访问根结点(D)；2)先序遍历左子树(L)；3)先序遍历右子树(R)先序遍历二叉树的递归算法:voidPreOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行先序遍历if(bt){visit(bt->data);//访问根结点PreOrderTraverse(bt->lchild);PreOrderTraverse(bt->rchild);}}//PreOrderTraverse先序遍历的调用过程：ADBCDLRADLRB>DLRD>>DLRC>>先序遍历序列：ABDC先序遍历二叉树的非递归算法（方法一）:voidPreOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行先序遍历if(bt){InitStack(S);Push(S,bt);//根指针进栈while(!StackEmpty(S)){while(GetTop(S,p)&&p){printf(p->data);Push(S,p->lchild);}//向左一直走到尽头Pop(S,p); //空指针退栈if(!StackEmpty(S)) {Pop(S,p);Push(S,p->rchild);}}//while}//if}//PreOrderTraverse先序遍历二叉树的非递归算法（方法二）:voidPreOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行先序遍历if(bt){InitStack(S);p=bt;Push(S,NULL);while(p){printf(p->data);if(p->rchild)Push(S,p->rchild);if(p->lchild)p=p->lchild;elsePop(S,p); }//while}//if}//PreOrderTraverse先序遍历二叉树的非递归算法（方法三）:voidPreOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行先序遍历if(bt){InitStack(S);p=bt;while(p||!StackEmpty(S)){while(p){printf(p->data);if(p->rchild)Push(S,p->rchild);p=p->lchild;}if(!StackEmpty(S))Pop(S,p); }//while}//if}//PreOrderTraverse2、中序遍历二叉树中序遍历二叉树的操作定义:若二叉树为空，则空操作；否则1)中序遍历左子树(L)；2)访问根结点(D)；3)中序遍历右子树(R)中序遍历二叉树的递归算法:voidInOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行中序遍历if(bt){InOrderTraverse(bt->lchild);visit(bt->data);//访问根结点InOrderTraverse(bt->rchild);}}//InOrderTraverse中序遍历的调用过程：LDRLDR>BLDR>D>ALDR>C>中序遍历序列：BDACADBC中序遍历二叉树的非递归算法（方法一）:voidInOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行中序遍历if(bt){InitStack(S);Push(S,bt);//根指针进栈while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左一直走到尽头Pop(S,p); //空指针退栈if(!StackEmpty(S)) {Pop(S,p);printf(p->data);Push(S,p->rchild);}}//while}//if}//InOrderTraverse中序遍历二叉树的非递归算法（方法二）:voidInOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行先序遍历if(bt){InitStack(S);p=bt;while(p||!StackEmpty(S)))

if(p){Push(S,p);p=p->lchild;else{Pop(S,p);printf(p->data);p=p->rchild;}}//if}//InOrderTraverse此处还可写成：{while(p){Push(S,p);p=p->lchild;}if(!StackEmpty(S)){Pop(S,p);printf(p->data);p=p->rchild;}}3、后序遍历二叉树后序遍历二叉树的操作定义:若二叉树为空，则空操作；否则1)后序遍历左子树(L)；2)后序遍历右子树(R)；3)访问根结点(D)后序遍历二叉树的递归算法:voidPostOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行后序遍历if(bt){PostOrderTraverse(bt->lchild);PostOrderTraverse(bt->rchild);visit(bt->data);//访问根结点}}//PostOrderTraverse后序遍历的调用过程：ADBCLRDLRD>LRD>>DBLRD>>CA后序遍历序列：DBCA后序遍历二叉树的非递归算法（方法一）:voidPostOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行后序遍历InitStack(S);Push(S,bt);//根指针进栈while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左一直走到尽头Pop(S,p); //空指针退栈if(!StackEmpty(S)){GetTop(S,p);

if(p->rchild)

Push(S,p->rchild);else{Pop(S,p);printf(p->data);while(!StackEmpty(S)&&GetTop(S,q)&&q->rchild==p){Pop(S,p);printf(p->data);}if(!StackEmpty(S)){GetTop(S,p);Push(S,p->rchild);}}}}}//PostOrderTraverse后序遍历二叉树的非递归算法（方法二）:voidPostOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行后序遍历InitStack(S);Push(S,NULL);p=bt;q=NULL;while(p||!StackEmpty(S)){if(p&&p!=q){Push(S,p);p=p->lchild;}else{Pop(S,p);if(!StackEmpty(S)) if(p->rchild&&p->rchild!=q){Push(S,p);p=p->rchild;}else{printf(p->data);q=p;}}}}//PostOrderTraverse后序遍历二叉树的非递归算法（方法三）:voidPostOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行后序遍历InitStack(S);p=bt;flag=1;do{while(p){Push(S,p);p=p->lchild;}q=NULL;flag=1;while(!StackEmpty(S)&&flag){GetTop(S,p);if(p->rchild==q){printf(p->data);Pop(S,p);q=p;} else{p=p->rchild;flag=0;}}}while(!StackEmpty(S));}//PostOrderTraverse通过上述介绍可以看到：三种遍历算法递归执行的(指针)路线相同，只是访问根结点的时机不同。如下图所示：-*abc-*cab-*abcabc*-abc-*4、层次遍历二叉树voidLevelOrderTraverse(BiTreebt){//二叉树bt采用二叉链表存储，对bt进行层次遍历if(bt){InitQueue(Q);EnQueue(Q,bt);while(!QueueEmpty(Q)){DeQueue(Q,p);printf(p->data);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild); }}}//LevelOrderTraverse5、按某种遍历序列建立二叉树的二叉链表例如按先序遍历序列建立二叉树的二叉链表，假设输入的字符顺序为：ABC□□DE□G□

□F□

□

□

（□表示空格），建立的二叉树如下图所示：voidCreateBiTree(BiTree&bt){//根据输入的字符建立二叉树bt的二叉链表scanf(&ch);if(ch==‘’)bt=NULL;else{if(!(bt=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);

bt->data=ch;CreateBiTree(bt->lchild);CreateBiTree(bt->rchild);}}//CreateBiTree遍历二叉树的有关说明：遍历二叉树的基本操作是访问结点，不论哪种次序进行遍历，对于含有n个结点的二叉树，其时间复杂度均为O(n)。对于非递归遍历算法所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，所以其空间复杂度也为O(n)。已知二叉树的先序遍历序列和中序遍历序列、

中序遍历序列和后序遍历序列以及层次遍历序列和中序遍历序列，均可唯一地确定一棵二叉树，如图；已知二叉树的先序遍历序列和后序遍历序列不能唯一地确定一棵二叉树，如图。已知二叉树的：先序序列：ABCDEFGHI中序序列：BCAEDGHFI构造的二叉树如右图所示：已知二叉树的：先序序列：AB后序序列：BA构造的二叉树如右图所示：基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结线索二叉树线索二叉树的必要性：无论以何种次序进行遍历，遍历二叉树的过程是以一定规则将二叉树中结点排列成一个线性序列，其实质是对一个非线性结构进行线性化操作，使每个结点(除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是以二叉链表作为存储结构时，只能找到结点的左右孩子信息，不能直接得到结点在任一序列中的前驱和后继信息。如何存储遍历过程中得到的关于结点的前驱和后继信息？简单办法：在每个结点上增加两个指针域，分别指向结点在遍历过程中得到的前驱和后继结点。缺点：浪费存储空间。最终思路：因为在有n个结点的二叉链表中必定存在n+1个空链域，因此应充分利用这些空链域来存放结点的前驱和后继信息。该方案最终导致线索二叉树的提出。线索二叉树的定义：lchildltagdatartagrchild其中：线索二叉树的存储结构：typedefenumPointerTag{Link,Thread};typedefstructBiThrNode{TElemType data;structBiThrNode*lchild,*rchild;

PointerTag

Ltag,Rtag;}BiThrNode,*BiThrTree以这种结点结构构成的二叉链表，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。带头结点的线索二叉树示例(中序)遍历线索二叉树在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时止。遍历的第一个结点：先序序列中第一个结点必为根结点；中序序列中第一个结点必为二叉树的最左下角的结点；后序序列中第一个结点必为二叉树的左子树的最右下角的结点。如何在线索二叉树的找结点的后继呢？根据不同的遍历方法，其后继结点的查找方法也不同。寻找当前结点p在中序遍历下的后继与前驱if(p->RTag==Thread)后继为p->rchildelse//p->RTag==Link后继为当前结点右子树最左下的结点if(p->LTag==Thread)前驱为p->lchildelse//p->LTag==Link前驱为当前结点左子树的最右下的结点中序遍历序列：a+b*c-d-e/f中序遍历线索二叉树voidInOrderTraverse_Thr(BiThrTreeT){//对带头结点的线索二叉树T进行中序遍历p=T->lchild//T为头指针,p指向根结点Link=0;Thread=1while(p!=T){//空树或遍历结束时p==T

{

while(p->LTag==Link)p=p->lchild;//先找到第一个结点printf(“%c”,p->data);

while(p->Rtag==Thread&&p->rchild!=T)

{p=p->rchild;printf(“%c”,p->data);}//访问后继结点p=p->rchild;}}//InOrderTraverse_Thr二叉树的线索化线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此，线索化的过程即为在遍历的过程中修改空指针的过程，算法描述如下：voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(0);Thrt->LTag=Link;Thrt->RTag=Thread;//建立头结点Thrt->rchild=Thrt;//右指针回指if(!T)Thrt->lchild=Thrt;//若二叉树空，则左指针回指else{Thrt->lchild=T;pre=Thrt;

InThreading(T);//中序遍历进行中序线索化pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化Thrt->rchild=pre;}}//InOrderThreading寻找当前结点p在先序遍历下的后继与前驱先序遍历线索二叉树voidPreOrder_Thr(BiThrTreeT){//T指向头结点，头结点的左链lchild指向根结点，先序遍历线索二叉树

p=T->lchild;//p指向根结点if(p){printf(p->data);while(p->rchild!=T){if(p->LTag==Link)p=p->lchild; elsep=p->rchild; printf(p->data);}}}//PreOrder_Thr先序线索化二叉树voidPreThreading(BiThrTreep){if(p){if(!p->lchild){p->LTag=Thread;p->lchild=pre;}if(!p->rchild)p->RTag=Thread;if(pre&&pre->RTag==Thread)pre->rchild=p;pre=p;if(p->LTag==Link)PreThreading(p->lchild);if(p->RTag==Link)PreThreading(p->rchild);}}//PreThreading寻找当前结点p在后序遍历下的后继与前驱后序遍历线索二叉树voidPostOrder_Thr(TriThrTreeT){{//T指向头结点，头结点的左链lchild指向根结点，后序遍历线索二叉树

p=T->lchild;do{while(p->LTag==Link)p=p->lchild;if(p->RTag==Link)p=p->rchild;}while(p->LTag!=Thread||p->RTag!=Thread);printf("%c",p->data);while(p!=T){if(p->RTag==Link){f=p->parent; if(f->RTag==Thread||p==f->rchild)p=f; else{p=f->rchild; do{while(p->LTag==Link)p=p->lchild;if(p->RTag==Link)p=p->rchild;}while(p->LTag!=Thread||p->RTag!=Thread);}}elsep=p->rchild;printf("%c",p->data);}}//PostOrder_Thr后序线索二叉树voidPostThreading(TriThrTreep){if(p){PostThreading(p->lchild);PostThreading(p->rchild);if(!p->lchild){p->LTag=Thread;p->lchild=pre;}if(!p->rchild)p->RTag=Thread;if(pre&&pre->RTag==Thread)pre->rchild=p;pre=p;}}//PostThreading优点：对于遍历操作，线索树优于非线索树，遍历线索树不用设栈voidInThreading(BiThrTreep){//中序线索化if(p){InThreading(p->lchild);//左子树线索化if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//前驱线索if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}//后继线索pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索}}//InThreading基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结1、树的存储结构（1）双亲表示法以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下：#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构TElemType data;int parent;//双亲位置域}PTNode;typedefstruct{//树结构PTNodenodes[MAX_TREE_SIZE];int r,n;//根的位置和结点数}PTree树和森林树的双亲表示法示例RABCDEFGHK-10123456789000113666数组下标优点：PARENT(T,x)操作可以在常量时间内实现缺点：求结点的孩子时需要遍历整个结构（2）孩子表示法：由于树中每个结点有多棵子树，可使用多重链表表示树，其每个结点有多个指针域，其中每个指针指向一棵子树的根结点。其结点有如下两种格式。如下图：child1datachild2childd…degreedatachild1child2childd…第一种格式：结点同构，链表中会产生许多空链域，浪费空间；容易证明：在一棵有点n个结点度为k的树中必有n(k-1)+1个空链域。第二种格式：结点不同构，空间比较节约，但操作不方便。另外一种办法：每个结点的孩子排列起来，看成一个线性表，以单链表作为存储结构。则n个结点有n个孩子链表（叶子的孩子链表为空表）。n个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];int n,r;//结点数和根的位置;}CTree;树的孩子链表表示法示例优点：CHILD(T,i,&x)操作可以在常量时间内实现缺点：PARENT(T,x)需要遍历整个结构解决方法：将双亲表示法和孩子表示法结合起来进行操作（3）孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉链表做树的存储结构，链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。其形式说明如下：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;树的孩子兄弟表示法示例优点：便于实现各种树的操作2、森林与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构来看，他们的二叉链表表示相同，只是解释不同。如图所示树的根结点无兄弟结点，其对应的二叉树的右子树必为空。若把森林中的第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可以导出森林与二叉树之间的对应关系。树转换成二叉树的方法(1)在同胞兄弟之间加连线；ABCEDABCED(2)保留结点与第一个孩子之间的连线，去掉其余连线；ABCED(3)将结点与孩子之间的连线调整为垂直线，将同胞兄弟之间的连线调整为水平线；ABCED(4)以根结点为轴，顺时针旋转45度。二叉树转换成树的方法(1)将每个结点的左孩子沿及其右链访问到的所有结点与左孩子的双亲之间加连线；(2)将结点与右链之间的连线去掉；(3)将所有的兄弟结点调整在同一水平线上，并作适当的角度调整。森林转换成二叉树的方法(1)将每棵树转化成二叉树；(2)将第一棵树的树根作为整棵二叉树的树根；(3)将剩余的每棵树依次连接到二叉树的右子树上。3、树与森林的遍历树的遍历有两种：先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；（等价于二叉树的先序遍历）后根遍历：先依次后根遍历每棵子树，然后访问根结点。（等价于树的中序遍历）先根序列：ABCDE后根序列：BDCEA先序遍历森林：若森林非空，则按下述规则遍历之(1)访问森林中第一棵树的根结点；(2)先序遍历第一棵树中根结点的子树森林；(3)先序遍历除去第一棵树之后剩余的树构成的森林。（等价于二叉树的先序遍历）森林的遍历有两种：中序遍历森林：若森林非空，则按下述规则遍历之(1)中序遍历第一棵树的根结点的子树森林；(2)访问第一棵树的根结点；(3)中序遍历除去第一棵树之后剩余的树构成的森林。（等价于二叉树的中序遍历）先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG基本内容树的定义和基本术语二叉树的定义及性质二叉树的存储结构遍历二叉树线索二叉树哈夫曼树及其应用树和森林本章小结哈夫曼（Huffman）树及其应用1、相关概念路径和路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度：从树根到每一个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：哈夫曼树：带权路径长度WPL最小的二叉树称作赫夫曼树或最优二叉树。(1)WPL=7*2+5*2+2*2+4*2=36(2)WPL=7*3+5*3+2*1+4*2=46(3)WPL=7*1+5*2+2*3+4*3=35（哈夫曼树）2、构造哈夫曼树（哈夫曼算法）（1）根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti只有一个带权为wi的根结点,其左右子树为空;（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和；（3）在F中删除这两棵树，同时将新得到的二叉树加入F中；（4）重复（2）和（3），直到F中只含一棵二叉树为止。这棵树便是哈夫曼树。赫夫曼树构造过程示例1赫夫曼树构造过程示例2(非唯一性)WPL1=(2+4+5+6)*2=34WPL2=6*1+5*2+2*3+4*3=343、哈夫曼树应用实例——判定问题在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。通常的编写形式如下：if(score<60)printf(“bad”);elseif(score<70)printf(“pass”);elseif(score<80)printf(“general”);elseif(score<90)printf(“good”);esleprintf(“verygood”);Ya<60a<70a<80a<90不及格优秀及格良好中等YYYNNNN在实际应用中，往往各个分数段的分布并不是均匀的。例如某门课程的各分数段的分布情况如下：比例数分数0—5960—6970—7980—8990—1000.050.150.400.300.10为了使程序运行的更有效率（也就是尽量减少程序运行过程中的比较次数），可以使用赫夫曼算法建立该问题的最佳判定树。以5,15,40,30和10为权构造一棵有5个结点的赫夫曼树如下：70≤a<8080≤a<9060≤a<70a<60不及格优秀及格良好中等YYYYNNNNa<80a<90a<70a<60不及格优秀及格良好中等YYYYNNN将判定框中的两次比较语句转化为单次比较语句，得最终判定树如上：4、哈夫曼编码编码的由来：在电文传输中，需要将电文中出现的每个字符进行二进制编码，即将传送的字符转换成二进制字符组成的字符串。例如，需传送的电文为“ABACCDA”通常有两类编码方式：等长编码和不等长编码等长编码：设A、B、C、D的编码分别为00、01、10、11。则上述7个字符的电文可转换为“00010010101100”。不等长编码：设A、B、C、D的编码分别为0、00、1、01。则上述7个字符的电文可转换为“000011010”。优点：编码长度短缺点：译码不唯一前缀编码：在设计不等长编码时，必须满足任一个字符的编码都不是另一个字符的前缀，这种编码也称作前缀编码。如何得到前缀编码？可以利用二叉树来设计二进制的前缀编码。假设如下图所示的二叉树，其4个叶子结点分别表示A、B、C、D这4个字符，且约定左右分支分别表示字符‘0’,‘1’。则可以将从根结点到叶子结点的路径上分支字符组成的字符