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