《数据结构第六章树和二叉树》由会员分享，可在线阅读，更多相关《数据结构第六章树和二叉树（62页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树第一节第一节树的类型定义树的类型定义A为为“根根”T1、T2和和T3都是一棵树，称为都是一棵树，称为A的的子树子树。称根和子树根之间的连线为称根和子树根之间的连线为“分支分支”结点分支的个数定义为结点分支的个数定义为“结点的度结点的度”，如结点，如结点B的度为的度为2，D的度为的度为3。树中所有结点度的最大值定义为树中所有结点度的最大值定义为“树的度树的度”。称度为零的结点为称度为零的结点为“叶子叶子”或或“终端结点终端结点”所有度不为零的结点所有度不为零的结点被称作被称作分支结点分支结点基本定义基本定义森林森林为为m(m0)棵互不相交的树的集合。棵互不相交的树的集合。树的深
2、度树的深度定义为树中叶子结点所在最大层次数。定义为树中叶子结点所在最大层次数。称根结点为子树根的称根结点为子树根的双亲双亲。称子树根为根结点的称子树根为根结点的孩子孩子“根的所有子树根互为根的所有子树根互为“兄弟兄弟”。有序树、无序树有序树、无序树如果树中如果树中每棵子树从左向右的排列拥有每棵子树从左向右的排列拥有一定的顺序，不得互换，则称一定的顺序，不得互换，则称为有序树，否则称为无序树。为有序树，否则称为无序树。树的抽象数据类型：树的抽象数据类型：ADTTree数据对象数据对象：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系：若若D为空集，则称为为空集，
3、则称为空树空树；若若D中仅含一个数据元素，则关系中仅含一个数据元素，则关系R为空集；为空集；否则否则R=H，(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root，它在关系它在关系H下无前驱；下无前驱；(2)当当n1时，其余数据元素可分为时，其余数据元素可分为m(m0)个个互不相交的互不相交的(非空非空)有限集有限集T1,T2,Tm,其中每一个子其中每一个子集本身又是一棵符合本定义的树，称为根集本身又是一棵符合本定义的树，称为根root的的子树子树，每一棵子树的根每一棵子树的根xi都是根都是根root的后继，即的后继，即H,i=1,2,m。基本操作基本操作：结构初始化结构
4、初始化InitTree(&T);操作结果：构造空树操作结果：构造空树T。CreateTree(&T,definition);初始条件：初始条件：definition给出树给出树T的定义。的定义。操作结果：按操作结果：按definition构造树构造树T。销毁结构销毁结构DestroyTree(&T);初始条件：树初始条件：树T存在。存在。操作结果：销毁树操作结果：销毁树T。引用型操作引用型操作TreeEmpty(T);初始条件：树初始条件：树T存在。存在。操作结果：若操作结果：若T为空树，则返回为空树，则返回TRUE，否则，否则返回返回FALSE。TreeDepth(T);初始条件：树初始条件
5、：树T存在。存在。操作结果：返回操作结果：返回T的的深度深度。Root(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的根。的根。Value(T,cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回cur_e的值。的值。Parent(T,cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非根结点，则返回它的的非根结点，则返回它的双亲双亲，否，否则返回则返回空空。LeftChild(T,cur_e);初始条件：树初始条
6、件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非叶子结点，则返回它的最的非叶子结点，则返回它的最左孩左孩子子，否则返回，否则返回空空。RightSibling(T,cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e有右兄弟，则返回它的有右兄弟，则返回它的右兄弟右兄弟，否则返，否则返回回空空。TraverseTree(T,visit();初始条件：树初始条件：树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按
7、某种次序对T的每个结点调用函数的每个结点调用函数visit()一一次且至多一次。一旦次且至多一次。一旦visit()失败，则操作失败。失败，则操作失败。加工型操作加工型操作Assign(T,cur_e,value);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：结点操作结果：结点cur_e赋值为赋值为value。ClearTree(&T);初始条件：树初始条件：树T存在。存在。操作结果：将树操作结果：将树T清为空树清为空树。InsertChild(&T,&p,i,c);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip所指
8、所指结点的度结点的度1，非空树，非空树c与与T不相交。不相交。操作结果：操作结果：插入插入c为为T中中p所指结点的第所指结点的第i棵子树。棵子树。DeleteChild(&T,&p,i);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip指结指结点的度。点的度。操作结果：操作结果：删除删除T中中p所指结点的第所指结点的第i棵子树。棵子树。ADTTree树和线性结构对照：树和线性结构对照：第二节第二节二叉树类型二叉树类型定义：定义：二叉树二叉树是另一种树形结构。它与树形是另一种树形结构。它与树形结构的区别是：结构的区别是：（1）每个结点最多有两棵子树；）每个结点最多
9、有两棵子树；（2）子树有左右之分。）子树有左右之分。二叉树也可以用递归的形式定义。二叉树也可以用递归的形式定义。即：二叉树是即：二叉树是n（n0）个结点的有限集合。）个结点的有限集合。当当n=0时，称为时，称为空二叉树空二叉树；当；当n0时，有且时，有且仅有一个结点为二叉树的仅有一个结点为二叉树的根根，其余结点被分，其余结点被分成两个互不相交的子集，一个作为成两个互不相交的子集，一个作为左子集左子集，另一个作为另一个作为右子集右子集，每个子集又是一个二叉，每个子集又是一个二叉树。树。二叉树的二叉树的5种形态：种形态：(a)(b)(c)(d)(e)6.2.1二叉树的类型定义二叉树的类型定义ADT
10、BinaryTree数据对象数据对象：D是具有相同特性的数据元素的集是具有相同特性的数据元素的集合。合。数据关系数据关系：若若D为空集，称为空集，称BinaryTree为为空二叉树空二叉树；否则否则关系关系R=H：(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root，它在关系，它在关系H下无前驱；下无前驱；(2)D中其余元素中其余元素必可分为必可分为两个互不相交的两个互不相交的子集子集L和和R，每一个子集都是一棵符合本定义的二，每一个子集都是一棵符合本定义的二叉树，并分别为叉树，并分别为root的的左子树左子树和和右子树右子树。如果左子。如果左子树树L不空，则必存在一个
11、根结点不空，则必存在一个根结点，它是，它是root的的左左后继后继(H)，如果右子树，如果右子树R不空，则必存不空，则必存在一个根结点在一个根结点为为root的的右后继右后继(H)。基本操作基本操作P：结构初始化结构初始化InitBiTree(&T);操作结果：构造操作结果：构造空空二叉树二叉树T。CreateBiTree(&T,definition);初始条件：初始条件：definition给出二叉树给出二叉树T的定义。的定义。操作结果：按操作结果：按definition构造二叉树构造二叉树T。销毁结构销毁结构DestroyBiTree(&T);初始条件：二叉树初始条件：二叉树T存在。存在。
12、操作结果：销毁二叉树操作结果：销毁二叉树T。引用型操作引用型操作BiTreeEmpty(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：若操作结果：若T为空二叉树，则返回为空二叉树，则返回TRUE，否，否则返回则返回FALSE。BiTreeDepth(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。Root(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的根。的根。Value(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的
13、值。的值。Parent(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：若操作结果：若e是是T的非根结点，则返回它的双亲，的非根结点，则返回它的双亲，否则返回否则返回空空。LeftChild(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的的左孩子左孩子。若。若e无左孩子，则返无左孩子，则返回回空空。RightChild(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的的右孩子右孩子。若。若e无右孩子，
14、则返无右孩子，则返回回空空。LeftSibling(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的的左兄弟左兄弟。若。若e是其双亲的左孩是其双亲的左孩子或无左兄弟，则返回子或无左兄弟，则返回空空。RightSibling(T,e);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T的结点。的结点。操作结果：返回操作结果：返回e的的右兄弟右兄弟。若。若e是其双亲的右孩子或无右是其双亲的右孩子或无右兄弟，则返回兄弟，则返回空空。PreOrderTraverse(T,visit();初始条件：二叉树初始条件：二叉树T存在存
15、在,visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：先序遍历先序遍历T，对每个结点调用函数，对每个结点调用函数visit一次且一次且仅一次。一旦仅一次。一旦visit()失败，则操作失败。失败，则操作失败。InOrderTraverse(T,vsit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：中序遍历中序遍历T，对每个结点调用函数，对每个结点调用函数Visit一次且一次且仅一次。一旦仅一次。一旦visit()失败，则操作失败。失败，则操作失败。PostOrderTraverse(
16、T,visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：后序遍历后序遍历T，对每个结点调用函数，对每个结点调用函数visit一次且一次且仅一次。一旦仅一次。一旦visit()失败，则操作失败。失败，则操作失败。LevelOrderTraverse(T,visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作是对结点操作的应用函数。的应用函数。操作结果：操作结果：层序遍历层序遍历T，对每个结点调用函数，对每个结点调用函数visit一次且仅一次。一旦一次且仅一次。一旦visit()失
17、败，则操作失败。失败，则操作失败。加工型操作加工型操作ClearBiTree(&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：将二叉树操作结果：将二叉树T清为空树清为空树。Assign(&T,&e,value);初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。操作结果：结点操作结果：结点e赋值为赋值为value。InsertChild(&T,p,LR,c);初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1，非空二叉树，非空二叉树c 与与 T 不相交且右子树为空。不相交且右子树为空。操作结果：操作结果
18、：根据根据LR为为0或或1，插入，插入c为为T中中p所指结点的左或右子树。所指结点的左或右子树。p所指结点原有左或右子树成所指结点原有左或右子树成为为c的右子树。的右子树。DeleteChild(&T,p,LR);初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1。操作结果：根据操作结果：根据LR为为0或或1，删除，删除T中中p所指所指结点的左或右子树。结点的左或右子树。ADTBinaryTree6.2.2二叉树的几个特性二叉树的几个特性一、在二叉树的第一、在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i1)。二、深度为二、深度为k的二
19、叉树中至多含有的二叉树中至多含有2k-1个结点，个结点，(k1)。三、对任何一棵二叉树三、对任何一棵二叉树T，如果其终端结点数，如果其终端结点数为为n0，度为，度为2的结点数为的结点数为n2，则，则n0=n2+1若二叉树中所有的分支结点的度数都为若二叉树中所有的分支结点的度数都为2，且，且叶子结点都在同一层次上，则称这类二叉树为叶子结点都在同一层次上，则称这类二叉树为满二叉树满二叉树。假如一棵包含假如一棵包含n个结点的二叉树中每个结点个结点的二叉树中每个结点都可以和满二叉树中编号为都可以和满二叉树中编号为1至至n的结点一、的结点一、一对应，则称这类二叉树为一对应，则称这类二叉树为完全二叉树完全
20、二叉树。第三节第三节二叉树的存储表示二叉树的存储表示6.3.1顺序存储结构顺序存储结构二叉树的顺序存储结构的定义如下：二叉树的顺序存储结构的定义如下：constMAXSIZE=100;/暂定二叉树中结点数的最大值为暂定二叉树中结点数的最大值为100typedefstructElemType*data;/存储空间基址存储空间基址(初始化时分配空间初始化时分配空间)intnodeNum;/二叉树中结点数二叉树中结点数SqBiTree;/二叉树的顺序存储结构二叉树的顺序存储结构6.3.2链式存储结构链式存储结构二叉树的二叉链表存储表示二叉树的二叉链表存储表示typedefstructBiTNodeE
21、lemTypedata;structBiTNode*Lchild,*Rchild;/左、右孩子指左、右孩子指针针*BiTree;二叉树的三叉链表存储表示二叉树的三叉链表存储表示typedefstructTriTNodeElemTypedata;structBiTNode*Lchild,*Rchild;/左、右孩子指左、右孩子指针针structBiTNode*parent;/双亲指针双亲指针*TriTree;二叉树的双亲链表存储表示二叉树的双亲链表存储表示typedefstructBPTNode/结点结构结点结构ElemTypedata;int*parent;/指向双亲的指针指向双亲的指针cha
22、rLRTag;/左、右孩子标志域左、右孩子标志域BPTNode第四节第四节二叉树的遍历二叉树的遍历“遍历遍历”的含义是对结构中的每个数据元的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。素都访问一次且仅仅访问一次。由于二叉树中每个结点都有两个后继，则由于二叉树中每个结点都有两个后继，则可以有三条搜索路径：可以有三条搜索路径：1)先先左左(子树子树)后后右右(子树子树)；2)先先右右(子树子树)后后左左(子树子树)；3)按层次从上到下。按层次从上到下。6.4.1先左后右的遍历先左后右的遍历6-4-1遍历遍历.swfG HD E FB CA先序序列：先序序列：ABDGCEFH中序序列：中序
23、序列：DGBAECHF后序序列：后序序列：GDBEHFCA先序遍历递归算法先序遍历递归算法voidPreOrder(BTreeBT)if(BT)Visit(BT);PreOrder(BT-Lchild);PreOrder(BT-Rchild);6-4-2-1.swf中序遍历递归算法中序遍历递归算法voidInOrder(BTreeBT)if(BT)InOrder(BT-Lchild);Visit(BT);InOrder(BT-Rchild);6-4-2-2.swf后序遍历递归算法后序遍历递归算法voidPostOrder(BTreeBT)if(BT)PostOrder(BT-Lchild);P
24、ostOrder(BT-Rchild);Visit(BT);6-4-2-3.swf按层次遍历二叉树按层次遍历二叉树按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：ABCDEFGHG HD E FB CA二叉树用链式存储结构表示时，按层遍历的算法实现二叉树用链式存储结构表示时，按层遍历的算法实现（1）访问根结点，并将根结点入队；）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：）当队列不空时，重复下列操作：l从队列退出一个结点；从队列退出一个结点；l若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；l若其有右孩子，则访问右孩子，并将
25、其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；G HD E FB CAvoidLevelOrder(BTree*BT)if(!BT)exit;InitQueue(Q);p=BT;/初始化初始化Visite(p);EnQueue(&Q,p);/访问根结点，并将根结点入队访问根结点，并将根结点入队while(!QueueEmpty(Q)/当队非空时重复执行下列操作当队非空时重复执行下列操作DeQueue(&Q,&p);/出队出队if(!p-Lchild)Visite(p-Lchild);EnQueue(&Q,p-Lchild);/处理处理左孩子左孩子if(!p-Rchild)Visi
26、te(p-Rchild);EnQueue(&Q,p-Rchild);/处理处理右孩子右孩子建立二叉建立二叉树voidCreateBiTree(BiTree&T)/在先序遍在先序遍历二叉二叉树的的过程中程中输入二叉入二叉树的的先序字符串先序字符串，/建立根指建立根指针为T的二叉的二叉链表存表存储结构。在先序字符串中，构。在先序字符串中，/字符字符#表示空表示空树，其它字母字符，其它字母字符为结点的数据元素点的数据元素cinch；if(ch=#)T=NULL;/建空建空树elseT=newBiTNode;/访问操作操作为生成根生成根结点点T-data=ch;CreateBiTree(T-Lchil
27、d);/递归建建(遍遍历)左子左子树CreateBiTree(T-Rchild);/递归建建(遍遍历)右子右子树6-4-6.swf统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数voidCountLeaf(BiTreeT,int&count)/先序遍历二叉树，以先序遍历二叉树，以count返回二叉树中叶子返回二叉树中叶子结点的数目结点的数目if(T)if(!T-Lchild)&(!T-Rchild)count+;/对叶子结点计数对叶子结点计数CountLeaf(T-Lchild,count);CountLeaf(T-Rchild,count);/if求二叉树的深度求二叉树的深度voidBi
28、TreeDepth(BiTreeT,intlevel,int&depth)/T指向二叉树的根，指向二叉树的根，level为为T所指结点所在层次，所指结点所在层次，其初值为其初值为1，depth为当前求得的最大层次为当前求得的最大层次,其初值为其初值为0if(T)if(leveldepth)depth=level;BiTreeDepth(T-Lchild,level+1,depth);BiTreeDepth(T-Rchild,level+1,depth);6-4-3求二叉树的深度求二叉树的深度.swf复制二叉树复制二叉树生成一个二叉树的结点的算法：生成一个二叉树的结点的算法：BiTNode*Ge
29、tTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)/生成生成一个一个其其元素元素值为值为item，左指针为，左指针为lptr，右指针为，右指针为rptr的结点的结点T=newBiTNode;T-data=item;T-Lchild=lptr;T-Rchild=rptr;returnT;后序后序遍历复制二叉树的操作为遍历复制二叉树的操作为:BiTNode*CopyTree(BiTNode*T)/已知二叉树的根指针为已知二叉树的根指针为T，本算法返回它的复制品的根指针，本算法返回它的复制品的根指针if(!T)returnNULL;/复制一棵空树复制
30、一棵空树if(T-Lchild)newlptr=CopyTree(T-Lchild);/复制复制(遍历遍历)左子左子树树elsenewlptr=NULL;if(T-Rchild)newrptr=CopyTree(T-Rchild);/复制复制(遍历遍历)右子右子树树elsenewrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生成根结点生成根结点returnnewnode;6-4-5后序遍历复制后序遍历复制.swf在二叉在二叉树上上查询某个某个结点点voidlocate(BiTreeT,ElemTypex,BiTree&p)/若二叉
31、若二叉树T中存在和中存在和x相同的元素，相同的元素，则p指指向向该结点，否点，否则p的的值不不变，p的初的初值为NULLif(T)if(T-data=x)p=T;locate(T-lchild,x,p);locate(T-rchild,x,p);中序遍历（非递归）中序遍历（非递归）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);if
32、(!Visit(p-data)returnERROR;Push(S,p-rchild);returnOK;表达式的二叉树表达式的二叉树二叉树的线索链表二叉树的线索链表将在二叉树中每个结点（除第一个和最后一个外）的直将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息是在遍历的动态接前驱和直接后继保存起来。这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行起来，则在以后再次需要对二叉树进行“遍历遍历”时就可时就可以将二叉树视作以将二叉树视作线性结构线性结构进行访问操
33、作了。进行访问操作了。typedefenumPointerTypeLink=0,Thread=1;/定义指针类型，以定义指针类型，以Link 表示指针表示指针，Thread 表示线表示线索索typedefstructBiThrNodeElemTypedata;structBiThrNode*Lchild,*Rchild;/左右指左右指针针PointerTypeLTag,RTag;/左右指针类型标志左右指针类型标志*BiThrTree;在线索链表中添加了一个在线索链表中添加了一个头结点头结点，头结点的，头结点的左指针左指针指向二叉树的指向二叉树的根根结点，其结点，其右线索右线索指向中指向中序序列
34、中的序序列中的最后最后一个结点一个结点以中序线索链表为存储结构的中序遍历以中序线索链表为存储结构的中序遍历voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(ElemTypee)/T指向中序线索链表中的头结点，头结点的左指针指向中序线索链表中的头结点，头结点的左指针Lchild指向二叉树的根结点，头结点的右线索指向二叉树的根结点，头结点的右线索Rchild指向中序遍历访指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对树中每问的最后一个结点。本算法对此二叉树进行中序遍历，对树中每个元素调用函数个元素调用函数Visit进行访问操作进行访问
35、操作p=T-Lchild;/p指向二叉树的根结点指向二叉树的根结点while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=Theadwhile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点访问其左子树为空的结点while(p-RTag=Thread&p-Rchild!=T)p=p-rchild;Visit(p-data);/访问访问“右线索右线索”所指所指后继结点后继结点p=p-Rchild;/p进至其右子树根进至其右子树根p=T-Lchild;/p指向二叉树的根结点指向二叉树的根结点while(p!=T)/空树或遍历结束时，空树或
36、遍历结束时，p=Theadwhile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点访问其左子树为空的结点while(p-RTag=Thread&p-Rchild!=T)p=p-rchild;Visit(p-data);/访问访问“右线索右线索”所指后继结点所指后继结点p=p-Rchild;/p进至其右子树根进至其右子树根6-5-1.swf线索链表的生成线索链表的生成voidInThreading(BiThrTreep，BiThrTree&pre)/对对p指向根结点的二叉树进行中序遍历，遍历过程指向根结点的二叉树进行中序遍历，遍历过程中进行中
37、进行“中序线索化中序线索化”。若。若p所指结点的左指针为空，则所指结点的左指针为空，则将它改为将它改为“左线索左线索”，若，若pre所指结点的右指针为空，则将所指结点的右指针为空，则将它改为它改为“右线索右线索”。指针。指针pre在遍历过程中紧随其后，即在遍历过程中紧随其后，即始终指向始终指向p所指结点在中序序列中的前驱。所指结点在中序序列中的前驱。if(p)InThreading(p-Lchild, pre);/对左子树进行线索化对左子树进行线索化if(!p-Lchild)p-LTag=Thread;p-Lchild=pre;/建前驱建前驱线索线索if(!pre-Rchild)pre-RTa
38、g=Thread;pre-Rchild=p;/建后建后继线索继线索pre=p;/保持保持pre指向指向p的前驱的前驱InThreading(p-Rchild, pre);/对右子树进行线索对右子树进行线索化化voidInOrderThreading(BiThrTree&Th,BiThrTreeBT)/BT为指向二叉树根结点的指针，由此二叉链表建立二叉为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链表，树的中序线索链表，Thead指向线索链表中的头结点。指向线索链表中的头结点。BiThrTreepre;if(!(Th=newBiThrNode)exit(1);/存储分配失败存储分配失
39、败Th-LTag=Link;Th-RTag=Thread;/建头结点建头结点Th-Rchild=Th;/右指针回指右指针回指if(!BT)Th-Lchild=Th;/若二叉树空，则左指针回指若二叉树空，则左指针回指elseTh-Lchild=BT;pre=Thead;InThreading(BT,pre);/中序遍历进行中序线索化中序遍历进行中序线索化pre-Rchild=Th;pre-RTag=Thead;/对中序序列对中序序列中最后一个结点进行线索化中最后一个结点进行线索化Th-Rchild=pre;/建非空树的头结点的建非空树的头结点的右线索右线索6-5-2.swf树和森林的存储表示树和
40、森林的存储表示1树的双亲表示法树的双亲表示法constMAX_TREE_SIZE=100;typedefstruct/结点结构结点结构ElemTypedata;intparent;/双亲位置域双亲位置域PTNode;typedefstruct/树结构树结构PTNodenodesMAX_TREE_SIZE;intr,n;/根的位置和结点数根的位置和结点数PTree;2树的孩子表示法树的孩子表示法树的孩子链表存储表示树的孩子链表存储表示typedefstructCTNode/孩子结点孩子结点intchild;structCTNode*next;*ChildPtr;typedefstructElem
41、Typedata;/结点的数据元素结点的数据元素ChildPtrfirstchild;/孩子链表头指针孩子链表头指针CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置结点数和根结点的位置CTree;3树和森林的孩子兄弟表示法树和森林的孩子兄弟表示法存储表示存储表示typedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;firstchild指向该结点的指向该结点的第一个第一个子树根结点，子树根结点，nextsibl
42、ing指向它的指向它的下一个下一个兄弟结点。兄弟结点。树的孩子树的孩子-兄弟链表兄弟链表森林的孩子森林的孩子-兄弟链表兄弟链表森林和二叉树的转换森林和二叉树的转换森林森林二叉树二叉树6-6-1.swf二叉树二叉树森林森林6-6-2.swf树的遍历树的遍历一、先根一、先根(次序次序)遍历树遍历树若树不空，则先访问根结点，然后依若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；次从左到右先根遍历根的各棵子树；ABEHIJCDFGK6-7-3.swf二、后根二、后根(次序次序)遍历树遍历树若树不空，则先依次从左到右后根遍若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；历
43、根的各棵子树，然后访问根结点；HIJEBCFKGDA6-7-4.swf森林的遍历森林的遍历一、先序遍历森林一、先序遍历森林若森林不空，则可依下列次序进行遍历若森林不空，则可依下列次序进行遍历(1)访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；(2)先序遍历第一棵树中的子树森林；先序遍历第一棵树中的子树森林；(3)先序遍历除去第一棵树之后剩余的树构成先序遍历除去第一棵树之后剩余的树构成的森林。的森林。二、中序遍历森林二、中序遍历森林若森林不空，则可依下列次序进行遍历：若森林不空，则可依下列次序进行遍历：(1)中序遍历第一棵树中的子树森林；中序遍历第一棵树中的子树森林；(2)访问森林中第
44、一棵树的根结点；访问森林中第一棵树的根结点；(3)中序遍历除去第一棵树之后剩余的树构成中序遍历除去第一棵树之后剩余的树构成的森林。的森林。求森林的深度求森林的深度森林的深度森林的深度=Max每一棵树的深度每一棵树的深度树的深度树的深度=其子树森林的深度其子树森林的深度+1intDepth_Tree(CSTreeT)/T是以孩子是以孩子-兄弟链表存储的森林的头指针，返回该森林的深兄弟链表存储的森林的头指针，返回该森林的深度度if(!T)return0;elsedep=0;/初始化森林的深度为初始化森林的深度为0p=T;/指针指针p指向第一棵树的根指向第一棵树的根while(p)d=Depth_Tree(p-firstchild);/返回返回*p的子树森林的的子树森林的深度深度if(d+1dep)dep=d+1;/求各棵树的深度的最大值求各棵树的深度的最大值p=p-nextsibling;/指针指针p移向下一棵树的移向下一棵树的根根returndep;
