数据结构树和二叉树演示文稿

数据结构PPT树和二叉树演示文稿当前第1页\共有101页\编于星期五\0点数据结构PPT树和二叉树当前第2页\共有101页\编于星期五\0点6.1树的定义和基本术语

什么是树？树是由n(n≥0)个结点的有限集合。如果n=0，称为空树；如果n>0，则

有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。当前第3页\共有101页\编于星期五\0点T={A，B，C，D，E，F，G，H，I，J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：T1={B，E，F，K，L}T2={C，G}T3={D，H，I，J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}T12={F}T11，T12是B的子树。HBAJFEDKLCMIG树的示例当前第4页\共有101页\编于星期五\0点1.树中只有根结点没有前趋；

2.除根外，其余结点都有且仅一个前趋；3.树的结点，可以有零个或多个后继；

4.除根外的其它结点，都存在唯一条从根到该结点的路径；5.树是一种分支结构。HBAJFEDKLCMIG树的逻辑结构特点当前第5页\共有101页\编于星期五\0点树可表示具有分支结构关系的对象例1.家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。例2.单位行政机构的组织关系HBAJFEDKLCMIG树的应用当前第6页\共有101页\编于星期五\0点树是常用的数据组织形式

有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。

例3.计算机的文件系统

不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹2文件1文件2文件夹11文件夹11文件11文件12C树的应用当前第7页\共有101页\编于星期五\0点树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG基本术语当前第8页\共有101页\编于星期五\0点结点的度：结点子树的个数；如D的度为3。叶子结点：也叫终端结点，是度为0的结点；如K、L、F、G、M、I、J。分支结点：度不为0的结点；如A、B、C、D结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树中各结点的度的最大值；如图所示树的度为3。森林：m(m>=0)棵互不相交的树的集合；HBAJFEDKLCMIG基本术语当前第9页\共有101页\编于星期五\0点线性结构第一个数据元素（无前驱）；最后一个数据元素（无后继）；其它数据元素（一个前驱、一个后继）。树型结构根结点（无前驱）；多个叶子结点（无后继）；其它数据元素（一个前驱、多个后继）。树型结构和线性结构的结构特点对比当前第10页\共有101页\编于星期五\0点6.2.1二叉树的定义或为空树，或由根及至多两棵互不相交的左子树、右子树构成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。说明：1.二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒——有序树；3.二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。BADCFEG6.2二叉树当前第11页\共有101页\编于星期五\0点φ(a)(b)(c)(d)(e)(a)空树(b)只含根结点(c)右子树为空树(d)左右子树均不为空树(e)左子树为空树LLRR二叉树的形态当前第12页\共有101页\编于星期五\0点性质1 在二叉树的第i层上至多有2i-1个结点。(i≥

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。6.2.2二叉树的性质当前第13页\共有101页\编于星期五\0点性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。证明：由性质1可见，深度为k的二叉树的最大结点数为

＝20+21+…+2k-1=2k-1＝6.2.2二叉树的性质当前第14页\共有101页\编于星期五\0点性质3对任何一棵二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则n0＝n2＋1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为：n＝n0＋n1＋n2

二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：n＝B＋1。由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2×n2;n＝B＋1＝n1＋2×n2＋1得到：n0＝n2＋16.2.2二叉树的性质当前第15页\共有101页\编于星期五\0点满二叉树：深度为k的二叉树，有2k-1个结点则称为满二叉树；完全二叉树：如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称为完全二叉树。完全二叉树的特点是：1.所有的叶结点都出现在第k层或k－1层。2.对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l＋1。两种特殊的二叉树当前第16页\共有101页\编于星期五\0点6217543891011131415126217543891011122154367216543非完全二叉树完全二叉树满二叉树两种特殊的二叉树当前第17页\共有101页\编于星期五\0点性质4：具有n个结点的完全二叉树的深度为

log2n

+1。证明：设完全二叉树的深度为k，则根据性质2和完全二叉树的定义有 2k-1-1<n≤2k-1或2k-1

≤n<2k取对数k-1<log2n≤k，又k是整数，因此有k=log2n＋16.2.2二叉树的性质当前第18页\共有101页\编于星期五\0点性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：

1.如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点i/2。

2.如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。

3.如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。6.2.2二叉树的性质当前第19页\共有101页\编于星期五\0点证明：此性质可采用数学归纳法证明。因为1与2、3是相对应的，所以只需证明2和3。当i=1时，根据结点编号方法可知，根的左、右孩子编号分别是2和3，结论成立。假定i-1时结论成立，即结点i-1的左右孩子编号满足：LCHILD(i-1)=2(i-1)；RCHILD(i-1)=2(i-1)+1通过完全二叉树可知，结点i或者与结点i-1同层且紧靠其右，或者结点i-1在某层最右端，而结点i在其下一层最左端。但是，无论如何，结点i的左孩子的编号都是紧接着结点i-1的右孩子的编号，故：LCHILD(i)=RCHILD(i-1)+1=2i；RCHILD(i)=LCHILD(i)+1=2i+1命题成立。6.2.2二叉树的性质当前第20页\共有101页\编于星期五\0点分析：根据完全二叉树的结构和编号规则，在i的左孩子前面的两个结点是结点i-1的左、右孩子，由归纳假设有：结点i-1的左孩子为2(i-1)，右孩子为2(i-1)+1。…...…...i与i+1同层…...…...i-12(i-1)2(i-1)+1i2i2i+1…...…...…...…...i与i+1不同层6.2.2二叉树的性质i2i2i+1i-12i-22i-1当前第21页\共有101页\编于星期五\0点最后证明结论1。当i=1时，显然根结点无双亲；当i＞1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论2知，x的左孩子应为2x，即2x=i，x=i/2；若是右孩子，由结论3知，x的右孩子应为2x+1，即2x+1=i，x=(i-1)/2。故i的双亲为└i/2┘证毕。6.2.2二叉树的性质当前第22页\共有101页\编于星期五\0点顺序存储结构所谓顺序存储结构，就是用一组连续的存储单元存储二叉树的数据元素，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。二叉树中结点之间的关系就是双亲结点与左右孩子结点间的关系。因此，必须把二叉树的所有结点安排成为一个恰当的序列。具体定义如下：#defineMAX-TREE-SIZE100TElemTypeSqBiTree[MAX-TREE-SIZE];

6.2.3二叉树的存储结构当前第23页\共有101页\编于星期五\0点通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。二叉树的顺序存储结构当前第24页\共有101页\编于星期五\0点FBAGEDCHIJKL例如：bt[3]的双亲为└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。如何反映结点之间的逻辑关系？A1B2C3D4E5F6G7H8I9J10K11L12完全二叉树的顺序表示当前第25页\共有101页\编于星期五\0点一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用Ø表示，Ø表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。A1B2C3D4Ø5E6F7G8H9Ø10Ø11Ø12Ø13I14J15EBAFDCGHIJØØØØØ例如对于B结点而言：bt[2]的双亲为└1/2┘=1，即在bt[1]中(为A)；其左孩子在bt[2i]=bt[4]中(为D)；其右孩子在bt[2i+1]=bt[5]中(为Ø)。一般二叉树的顺序表示当前第26页\共有101页\编于星期五\0点这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。例如，深度为k，且只有k个结点的右单支树(每个非叶结点只有右孩子)，也需2k-1个单元，即有(2k-1)-k个单元被浪费。12k顺序存储的优缺点当前第27页\共有101页\编于星期五\0点所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;链式存储结构当前第28页\共有101页\编于星期五\0点^D

AB^C^^E^^F^Tlchilddatarchild结点结构BADCEF二叉链表当前第29页\共有101页\编于星期五\0点ABCDEFG^^^^^^^^^三叉链表图示BACDEFG三叉链表lchilddata结点结构parentrchild当前第30页\共有101页\编于星期五\0点6.3遍历二叉树和线索二叉树6.3.1遍历二叉树定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。如何访问二叉树的每个结点且每个结点仅被访问一次？当前第31页\共有101页\编于星期五\0点由于二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。令L，R，D分别代表二叉树的左子树、右子树、根结点，则有DLR、LDR、LRD三种遍历规则。递归实现方法当前第32页\共有101页\编于星期五\0点若二叉树非空，则：1.访问根结点2.先序遍历左子树3.先序遍历右子树BADCDLRADLRDLR>B>>D>>CDLR得到的序列为：ABDC先序遍历二叉树当前第33页\共有101页\编于星期五\0点StatusPreOrderTraverse(BiTreeT){

//采用二叉链表存贮二叉树if(T){//若二叉树不为空Visit(T->data)；//访问根结点

PreOrderTraverse(T->lchild);//先序遍历T的左子树PreOrderTraverse(T->rchild);//先序遍历T的右子树

}//PreOrderTraverse先序遍历二叉树算法实现当前第34页\共有101页\编于星期五\0点viodpre(bintT){if(T)visite(T->data);pre(T->lchild);pre(T->rchild);}先序遍历二叉树算法实现BADC主程序Pre(T)TAvisite(A);pre(TL);TBvisite(B);pre(TL);T>返回pre(TR);TDvisite(D);pre(TL);T>返回pre(TR);T>返回pre(TR);TCvisite(C);pre(TL);T>返回pre(TR);T>返回先序序列：ABDC当前第35页\共有101页\编于星期五\0点若二叉树非空，则：1.中序遍历左子树2.访问根结点3.中序遍历右子树BADCLDRBLDRLDR>A>>D>>CLDR得到的序列为：BDAC中序遍历二叉树当前第36页\共有101页\编于星期五\0点若二叉树非空，则：1.后序遍历左子树2.访问根结点3.后序遍历右子树BADCLRDLRDLRD>A>>D>>CLRDB得到的序列为：DBCA后序遍历二叉树当前第37页\共有101页\编于星期五\0点*-bca这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。三种遍历过程示意图例-*abc当前第38页\共有101页\编于星期五\0点先序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。如此重复，直到栈为空或指针为空止。中序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空)为止，在走的过程中，把依次遇到的结点进栈，待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈空或指针为空止。非递归实现方法当前第39页\共有101页\编于星期五\0点statusInOrderTraverse(BiTreeT){InitStack(S);Push(S,T);//根结点进栈while(!StackEmpty(S){while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);//空指针退栈if(!StackEmpty(S)){Pop(S,p);Visit(p->data);Push(S,p->rchild);}}returnOK;}中序遍历的非递归算法当前第40页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)当前第41页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)当前第42页\共有101页\编于星期五\0点中序遍历的非递归算法演示pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)当前第43页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)当前第44页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->AP->D访问：CBEGp(10)当前第45页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)当前第46页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)当前第47页\共有101页\编于星期五\0点中序遍历的非递归算法演示ABCDEFGi访问：CBEGDFAp=NULL(15)当前第48页\共有101页\编于星期五\0点后序遍历：利用栈来实现二叉树的后序遍历要比先序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树，所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，元素第一次进栈标志为1，第二次进标志为2，当退出的元素标志为2时，访问结点。非递归实现方法当前第49页\共有101页\编于星期五\0点voidleaf(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化n=0if(T){

if(T->lchild==NULL&&T->rchild==NULL)n+=1;

//若T所指结点为叶子结点则计数leaf(T->lchild);leaf(T->rchild);}//if}//leaf例1编写求二叉树的叶子结点个数的算法当前第50页\共有101页\编于星期五\0点voidleaf(BiTreeT){If(T){

if(T->lchild==NULL&&T->rchild==NULL)n+=1;leaf(T->lchild);leaf(T->rchild);}//if}//leafStatusPreOrderTraverse(BiTreeT){

if(T){

Visit(T->data)；

PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}//PreOrderTraverse访问结点时统计叶子结点的个数访问结点时调用visit()比较先序遍历和计算叶子结点算法相同点和不同点当前第51页\共有101页\编于星期五\0点分析：本算法要借用队列来完成，其基本思想是，若二叉树非空，先将根结点进队列。然后进入循环：只要队列不空，就出队列，遍历该结点，然后判断出队列的结点是否有左孩子和右孩子，如有就让左、右孩子进队列。例2按层次遍历二叉树的算法当前第52页\共有101页\编于星期五\0点voidlayorder(BiTreeT){InitQueue(Q)//队列初始化if(T!=NULL){EnQueue(Q,T);//入队列while(notQueueEmpty(Q))//若队列非空{DeQueue(Q,p);//出队visite(p->data);if(p->lchild!=NULL)EnQueue(Q,p->lchild);//入队列if(p->rchild!=NULL)EnQueue(Q,p->rchild);//入队列}}}例2按层次遍历二叉树的算法当前第53页\共有101页\编于星期五\0点输入：二叉树的先序序列结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入在空子树处添加字符￠的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点链接。BADCEF￠￠￠￠￠￠￠在空子树处添加￠的二叉树的先序序列：ABD￠F￠￠E￠￠C￠￠例3建立二叉链表当前第54页\共有101页\编于星期五\0点StatusCreateBiTree(BiTree&T){//输入(在空子树处添加字符￠的二叉树的)先序序列(设元素均为字符)scanf(&ch);if(ch==‘￠’)T=NULL;//若ch==‘￠’则表示空子树else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//建立(根)结点

CreateBiTree(T->lchild);//递归构造左子树链表CreateBiTree(T->rchild);//递归构造右子树链表}returnOK;}//CreateBiTree建立二叉链表算法当前第55页\共有101页\编于星期五\0点建立二叉链表算法BACDAB

C

D

ABCDATBCD^^^^^当前第56页\共有101页\编于星期五\0点分析：由先序序列和中序序列的定义可知，先序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用先序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将先序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的先序序列;

4.对左、右子树的先序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。例4由二叉树先序和中序序列建立一个唯一二叉树当前第57页\共有101页\编于星期五\0点如一棵二叉树的先序序列为ABDGHCEFI，中序序列为GDHBAECIF，试建立该二叉树。构造过程：由先序可知A为根结点，再根据中序序列知：由GDHB是左子树，ECIF是右子树。A为根结点ABDGHCEFIGDHBAECIFB为左子树的根结点BDGHGDHB一直进行下去……AG,D,H,B组成左子树E,C,I,F组成右子树示例分析当前第58页\共有101页\编于星期五\0点abcdefgcbdaegfaabbccddeeffggabcdefg^^^^^^^^先序序列中序序列当前第59页\共有101页\编于星期五\0点遍历是二叉树最基本最常用的操作。

1.对二叉树所有结点做某种处理可在遍历过程中实现；

2.查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。6.3.2线索二叉树当前第60页\共有101页\编于星期五\0点定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。0lchild域指示结点的左孩子1lchild域指示结点的前驱0rchild域指示结点的右孩子1rchild域指示结点的后继以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。LTag=RTag=一、线索二叉树定义当前第61页\共有101页\编于星期五\0点利用现有的空指针域，每个n个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针。(n个结点共有2n个链域，而每个结点(除根结点外)都有一个分支指向，则共有n-1个分支，其中每个分支占有一个链域，所以空链域为2n-(n-1)=n+1。)若结点有左子树，则左指针lchild指示其左孩子(LTag=0)；否则，令左指针指示其前驱(LTag=1)；若结点有右子树，则右指针rchild指示其右孩子(RTag=0)；否则，令右指针指示其后继(RTag=1)。二、如何保存遍历过程中得到的信息？当前第62页\共有101页\编于星期五\0点typedefenumPointerTeg{Link,Thread};

//Link==0:指针，Thread==1:线索typedefstructBiThrNod{TElemTypedata;structBiThrNode*lchild,*rchild;//左右指针PointerTegLTag,RTag;//左右标志}BiThrNode,*BiThrTree;三、线索链表的类型描述lchildLTagdataRTagrchild当前第63页\共有101页\编于星期五\0点(以中序遍历为例)查找任意结点的前驱结点如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。中序线索二叉树中序：DBGJEACHLKFI四、如何找结点的前驱和后继BACEFDGJHIKL当前第64页\共有101页\编于星期五\0点中序线索二叉树中序：DBGJEACHLKFI四、如何找结点的前驱和后继(续)(以中序遍历为例)查找任意结点的后继结点对任意结点p，若右标志为1，则rchild指向该结点的后继；若右标志为0，则rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(Ltag=1)，则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点。BACEFDGJHIKL当前第65页\共有101页\编于星期五\0点按不同的方式遍历二叉树所得到的线索二叉树是不相同的。BADCE五、遍历线索二叉树ABDCET先序序列：ABCDE先序线索二叉树00001111^11ABDCET中序序列：BCAED中序线索二叉树00001111^11^ABDCET后序序列：CBEDA后序线索二叉树0000111111^当前第66页\共有101页\编于星期五\0点BADCEABDCET0000111111

01中序序列：BCAED中序线索二叉树五、遍历线索二叉树(续)带头结点的线索二叉树在存储线索二叉树时往往增设一头结点，其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。注：可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。当前第67页\共有101页\编于星期五\0点

找遍历的第一个结点左子树上处于“最左下”(没有左子树)的结点。

不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。遍历线索二叉树步骤(以中序遍历为例)当前第68页\共有101页\编于星期五\0点voidInOrderTraverse_Thr(BiThrTreeT){p=T->lchild;while(p!=T){while(p->LTag==0)p=p->lchild;Visit(p->data));while(p->RTag==1&&p->rchild!=T){p=p->rchild;Visit(p->data);}p=p->rchild;}}//InOrderTraverse_Thr中序线索二叉树中序：DBGJEACHLKFI中序遍历线索二叉树算法实现TBACEFDGJHIKL当前第69页\共有101页\编于星期五\0点建立线索二叉树，或者说对二叉树线索化，实质上是遍历一棵二叉树。在遍历过程中访问结点操作visit()是检查当前结点的左、右指针域是否为空，如果为空，将空的lchild改为结点的直接前驱，将空的rchild改为结点的直接后继。而对于非空指针，仍然指向孩子结点。为了记下遍历过程中访问结点的先后关系，附设指针pre始终指向刚刚被访问过的结点,若p指针指向当前访问的结点，则pre指向它的前驱。六、如何建立线索二叉树？当前第70页\共有101页\编于星期五\0点StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))exit(OVERFLOW);Thrt->LTag=0;Thrt->RTag=1;Thrt->rchild=Thrt;//添加头结点if(!T)Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;

InThreading(T);

pre->rchild=Thrt;//处理最后一个结点pre->RTag=1;Thrt->rchild=pre;}returnOK;}//InOrderThreadingThrt

01LR算法实现(1)：当前第71页\共有101页\编于星期五\0点voidleaf(BiTreeT){if(T){

leaf(T->lchild);

if(T->lchild==NULL&&T->rchild==NULL)n+=1;leaf(T->rchild);}}StatusPreOrderTraverse(BiTreeT){

if(T){PreOrderTraverse(T->lchild);

Visit(T->data)；

PreOrderTraverse(T->rchild);}算法实现(2)：当前第72页\共有101页\编于星期五\0点voidInThreading(BiThrTreep){if(p){

InThreading(p->lchild);//左子树线索化

if(!p->lchild)//建前驱线索{p->LTag=1;p->lchild=pre;}if(!pre->rchild)//建后继线索{pre->RTag=1;pre->rchild=p;}pre=p;//保持pre指向p的前驱

InThreading(p->rchild);//右子树线索化}//if}//InThreading相当于遍历算法中的visit()算法实现(2)：当前第73页\共有101页\编于星期五\0点6.4.1树的存贮结构一、双亲表示法：以一组连续的空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。其类型定义如下：#defineMAX_TREEE_SIZE100typedefstructPTNode{ElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}Ptree;特点：找双亲容易，找孩子难ARDCFEGBHKA0B0C0D1E1F3G6H6R-1K60123456789数组下标6.4树和森林当前第74页\共有101页\编于星期五\0点通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。多重链表：每个结点有多个指针域，分别指向其子树的根。结点同构：结点的指针个数相等，为树的度d。结点不同构：结点指针个数不等，为该结点的度d。datachild1child2……childddatadegreechild1child2……childd二、孩子表示法当前第75页\共有101页\编于星期五\0点孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。二、孩子表示法当前第76页\共有101页\编于星期五\0点ARDCFEGBHKAB^CD^E^FG^H^RK^0123456789数组下标125^43^789^6^特点：找孩子容易，找双亲难孩子链表表示法图示当前第77页\共有101页\编于星期五\0点typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置}CTree;孩子链表表示法类型定义当前第78页\共有101页\编于星期五\0点用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。特点：操作容易，但破坏了树的层次。孩子兄弟表示法类型定义：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;三、孩子兄弟表示法当前第79页\共有101页\编于星期五\0点ARDCFEGBHKR^AD^

B^

E^∧C

^F

∧G^

H^

K^^利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如找某结点的第i个孩子，则只要先从左指针域中找到第1个孩子结点上，然后沿着孩子结点的next域连续走i-1步便可找到第i个孩子。如增加一个parent域，则也能方便实现求双亲的操作。三、孩子兄弟表示法当前第80页\共有101页\编于星期五\0点一.树转变为二叉树加线：在兄弟之间加一连线；抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；旋转：以树的根结点为轴心，将整树顺时针转45°。6.4.2树、森林与二叉树转换当前第81页\共有101页\编于星期五\0点BAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFI由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。树转变为二叉树实现过程当前第82页\共有101页\编于星期五\0点由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。具体的方法如下：将各棵树分别转换成二叉树；将每棵树的根结点用线相连；以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。二、森林转换成二叉树当前第83页\共有101页\编于星期五\0点HIGJBADCEFHIGJBADCEFHIGJBADCEFHIGMBADCEF森林转变为二叉树实现过程当前第84页\共有101页\编于星期五\0点加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……，沿分支找到的所有右孩子，都与p的双亲用线连起来；抹线：抹掉原二叉树中双亲与右孩子之间的连线；调整：将结点按层次排列，形成树结构。BAEDGHCFIBAEDGHCFIBAEDGHCFI注：该二叉树的右子树为空三、二叉树转换成树当前第85页\共有101页\编于星期五\0点抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。HIGMBADCEFHIGJBADCEF注：该二叉树的右子树一定不为空四、二叉树转换成森林当前第86页\共有101页\编于星期五\0点在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，即树和森林只有先序遍历和后序遍历。1.树的先序遍历若树非空，则先访问根结点，然后依次先序遍历各子树。先序遍历：ABEFIGCDHJKLNOM2.树的后序遍历若树非空，则依次后序遍历各子树，最后访问根结点。后序遍历：EIFGBCJKNOLMHDA6.4.3树和森林的遍历ACBDEFGIHJKLMNO当前第87页\共有101页\编于星期五\0点3.森林的先序遍历若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、…、直到最后一棵树。遍历结果：ABCDEFGHIJ4.森林的后序遍历按顺序后序遍历森林中的每一棵树。遍历结果：BCDAFEHJIG6.4.3树和森林的遍历HIGJBADCEF当前第88页\共有101页\编于星期五\0点

一、基本概念路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。6.6赫夫曼树及其应用当前第89页\共有101页\编于星期五\