数据结构严蔚敏第6章学习教案.pptx

会计学1数据结构数据结构(sh j ji u)严蔚敏第严蔚敏第6章章第一页，共141页。第1页/共141页第二页，共141页。 1数据(shj)的逻辑结构 2、数据的存储(cn ch)结构 3、数据的运算：检索、排序(pi x)、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个主要问题 第2页/共141页第三页，共141页。树形结构树形结构(jigu)全校学生档案管理的组织全校学生档案管理的组织(zzh)方式方式第3页/共141页第四页，共141页。ABCDEFGH树形结构树形结构 结点间具有结点间具有(jyu)分层次的连接关系分层次的连接关系HBCDEFGA第4页/共141页第五页，共141页。6.1 树的类型定义树的类型定义6.2 6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储二叉树的存储(cn ch)结构结构6.4 二叉树的遍历二叉树的遍历(bin l)6.5 线索线索(xin su)二叉树二叉树6.6 树和森林的表示方法树和森林的表示方法6.7 树和森林的遍历树和森林的遍历6.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码第5页/共141页第六页，共141页。6.1 树的类型定义树的类型定义第6页/共141页第七页，共141页。数据数据(shj)对象对象 D：D是具有相同特性是具有相同特性(txng)的数据元素的集合。的数据元素的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子(k zi)集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系数据关系 R：第7页/共141页第八页，共141页。ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根(sh n)例如例如(lr):(lr):第8页/共141页第九页，共141页。 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类第9页/共141页第十页，共141页。 Root(T) / 求树的根结点(ji din) 查找查找(ch zho)类：类：Value(T, cur_e) / 求当前求当前(dngqin)结点的元素值结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历第10页/共141页第十一页，共141页。InitTree(&T) / 初始化置空树初始化置空树 插入插入(ch r)类：类：CreateTree(&T, definition) / 按定义按定义(dngy)构造树构造树Assign(T, cur_e, value) / 给当前给当前(dngqin)结点赋值结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树第11页/共141页第十二页，共141页。 ClearTree(&T) / 将树清空(qn kn) 删除删除(shnch)类：类：DestroyTree(&T) / 销毁销毁(xiohu)树的结构树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树第12页/共141页第十三页，共141页。对比树型结构对比树型结构(jigu)和线和线性结构性结构(jigu)的结构的结构(jigu)特点特点第13页/共141页第十四页，共141页。线性结构线性结构(jigu)树型结构树型结构(jigu)第一个数据第一个数据(shj)(shj)元素元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第14页/共141页第十五页，共141页。基基 本本 术术 语语第15页/共141页第十六页，共141页。结点结点(ji din):(ji din):结点结点(ji din)(ji din)的度的度: :树的度树的度: :叶子叶子(y zi)(y zi)结点结点: :分支结点分支结点: :数据元素+ +若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第16页/共141页第十七页，共141页。(从根到结点(ji din)的)路径：孩子孩子(hi zi)(hi zi)结点、双亲结点结点、双亲结点兄弟结点、堂兄弟兄弟结点、堂兄弟祖先结点、子孙结点祖先结点、子孙结点结点结点(ji din)(ji din)的层次的层次: :树的深度：树的深度： 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次第17页/共141页第十八页，共141页。任何一棵非空树是一个二元组 Tree = （root，F）其中(qzhng)：root 被称为根结点 F 被称为子树森林森林森林(snln)：是m（m0）棵互不相交(xingjio)的树的集合ArootBCDEFGHIJMKLF第18页/共141页第十九页，共141页。6.2 二叉树的类型定义二叉树的类型定义第19页/共141页第二十页，共141页。 二叉树或为空树，或是由一个根结点加上两棵分别称为(chn wi)左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点(ji din)左子树右子树第20页/共141页第二十一页，共141页。二叉树的五种基本二叉树的五种基本(jbn)形态：形态：N空树空树只含根结点只含根结点(ji din)NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右左右(zuyu)子树子树均不为均不为空树空树第21页/共141页第二十二页，共141页。 二叉树的主要二叉树的主要(zhyo)基本操作：基本操作：查查 找找 类类插插 入入 类类删删 除除 类类第22页/共141页第二十三页，共141页。 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();第23页/共141页第二十四页，共141页。 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);第24页/共141页第二十五页，共141页。ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);第25页/共141页第二十六页，共141页。二叉树二叉树的重要的重要(zhngyo)特性特性第26页/共141页第二十七页，共141页。用归纳法证明用归纳法证明(zhngmng)： 归纳基：归纳基： 归纳假设：归纳假设： 归纳证明归纳证明(zhngmng)：i = 1 层时，只有层时，只有(zhyu)一个根结点：一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。第27页/共141页第二十八页，共141页。证明证明(zhngmng)： 基于上一条性质，深度为 k 的二叉树上的结点(ji din)数至多为 20+21+ +2k-1 = 2k-1 。第28页/共141页第二十九页，共141页。证明证明(zhngmng)：设设 二叉树上结点二叉树上结点(ji din)总数总数 n = n0 + n1 + n2又又 二叉树上分支总数二叉树上分支总数 b = n1+2n2 而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。第29页/共141页第三十页，共141页。两类特殊两类特殊(tsh)的二叉树：的二叉树：满二叉树：指的是满二叉树：指的是深度为深度为k且含有且含有(hn yu)2k-1个结点的个结点的二叉树。二叉树。完全二叉树：树完全二叉树：树中所含的中所含的 n 个结个结点点(ji din)和满和满二叉树中编号为二叉树中编号为 1 至至 n 的结点的结点(ji din)一一对应。一一对应。12345678910 11 121314 15abcdefghij第30页/共141页第三十一页，共141页。 性质性质 4 ： 具有具有 n 个结点个结点(ji din)的完全的完全二叉树的深度为二叉树的深度为 log2n +1 。证明证明(zhngmng)：设完全二叉树的深度为设完全二叉树的深度为 k 则根据第二条性质得则根据第二条性质得 2k-1 n 2k 即即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。第32页/共141页第三十三页，共141页。6.3 二叉树的存储二叉树的存储(cn ch)结构结构二、二叉树的链式二、二叉树的链式 存储存储(cn ch)(cn ch)表示表示一、一、 二叉树的顺序二叉树的顺序(shnx) 存储表示存储表示第33页/共141页第三十四页，共141页。#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元号单元(dnyun)存储根结点存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示(biosh)第34页/共141页第三十五页，共141页。例如例如(lr):ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326顺序存储结构顺序存储结构(jigu)仅适用于完全二叉树！仅适用于完全二叉树！第35页/共141页第三十六页，共141页。二、二叉树的链式存储二、二叉树的链式存储(cn ch)(cn ch)表示表示1. 1. 二叉链表二叉链表2三叉链表三叉链表3 3双亲双亲(shungqn)(shungqn)链表链表4线索线索(xin su)链表链表第36页/共141页第三十七页，共141页。ADEBCF rootlchild data rchild结点结点(ji din)结构结构:1. 1. 二叉链表二叉链表第37页/共141页第三十八页，共141页。typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右左右(zuyu)孩子指针孩子指针 BiTNode, *BiTree;lchild data rchild结点结点(ji din)结构结构:C 语言的类型描述(mio sh)如下:第38页/共141页第三十九页，共141页。ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结点(ji din)结构结构:第39页/共141页第四十页，共141页。 typedef struct TriTNode / 结点(ji din)结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结点(ji din)结构结构:C 语言的类型(lixng)描述如下:第40页/共141页第四十一页，共141页。0123456B2C0A -1D2E3F4 data parent结点结点(ji din)结构结构:3 3双亲双亲(shungqn)(shungqn)链表链表LRTagLRRRL第41页/共141页第四十二页，共141页。 typedef struct BPTNode / 结点(ji din)结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点(ji din)数目 int root; / 根结点(ji din)的位置 BPTree第42页/共141页第四十三页，共141页。6.4二叉树的遍历二叉树的遍历(bin l)第43页/共141页第四十四页，共141页。一、问题一、问题(wnt)的提出的提出二、先左后右的遍历二、先左后右的遍历(bin l)算法算法三、算法三、算法(sun f)的递归描述的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例第44页/共141页第四十五页，共141页。 顺着某一条搜索路径巡访二叉树中的结点，使得(sh de)每个结点均被访问一次，而且仅被访问一次。一、问题一、问题(wnt)的提出的提出“访问”的含义可以(ky)很广，如：输出结点的信息等。第45页/共141页第四十六页，共141页。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条(y tio)搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点每个结点(ji din)有两个后继，有两个后继，则存在如何遍历即按什么样的搜索则存在如何遍历即按什么样的搜索路径遍历的问题。路径遍历的问题。第46页/共141页第四十七页，共141页。第47页/共141页第四十八页，共141页。二、先左后右的遍历二、先左后右的遍历(bin l)算法算法先序（根）的遍历先序（根）的遍历(bin l)算法算法中序（根）的遍历中序（根）的遍历(bin l)算法算法后后序（根）的遍历算法第48页/共141页第四十九页，共141页。 若二叉树为空树，则空操作；否则(fuz)，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先序（根）的遍历先序（根）的遍历(bin l)算法：算法：第49页/共141页第五十页，共141页。 若二叉树为空树，则空操作(cozu)；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中序（根）的遍历中序（根）的遍历(bin l)算法：算法：第50页/共141页第五十一页，共141页。 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问(fngwn)根结点。后序后序(hu x)（根）的遍历算法：（根）的遍历算法：第51页/共141页第五十二页，共141页。ABCDE第52页/共141页第五十三页，共141页。三、算法三、算法(sun f)的递归描述的递归描述void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树先序遍历二叉树 if (T) visit(T-data); / 访问访问(fngwn)结点结点 Preorder(T-lchild, visit); / 遍历左子树遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树遍历右子树 第53页/共141页第五十四页，共141页。四、中序遍历四、中序遍历(bin l)算法的非递归描述算法的非递归描述BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; 第54页/共141页第五十五页，共141页。void Inorder_I(BiTree T, void (*visit) (TelemType& e) Stack *S; t = GoFarLeft(T, S); / 找到最左下的结点找到最左下的结点(ji din) while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束栈空表明遍历结束 / while/ Inorder_I 第55页/共141页第五十六页，共141页。五、遍历五、遍历(bin l)算法的应用举例算法的应用举例1、统计二叉树中叶子结点、统计二叉树中叶子结点(ji din)的个数的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序后序(hu x)遍历遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构第56页/共141页第五十七页，共141页。1、统计二叉树中叶子、统计二叉树中叶子(y zi)结点的个结点的个数数算法算法(sun f)(sun f)基本思想基本思想: : 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数(cnsh)，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。第57页/共141页第五十八页，共141页。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子对叶子(y zi)结点计数结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf第58页/共141页第五十九页，共141页。2、求二叉树的深度、求二叉树的深度(shnd)(后序遍历后序遍历)算法基本算法基本(jbn)(jbn)思想思想: : 从二叉树深度的定义(dngy)可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子树右子树深度深度之间的关系。第59页/共141页第六十页，共141页。int Depth (BiTree T ) / 返回返回(fnhu)二叉树二叉树的深度的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第60页/共141页第六十一页，共141页。3、复制、复制(fzh)二叉树二叉树其基本操作为：生成一个其基本操作为：生成一个(y )(y )结点。结点。根元素根元素(yun s)T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)第61页/共141页第六十二页，共141页。BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据其数据(shj)域为域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)第62页/共141页第六十三页，共141页。BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制(fzh)左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制(fzh)右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree第63页/共141页第六十四页，共141页。ABCDEFGHK D C B H K G F E A例如：下列二叉树例如：下列二叉树的复制过程的复制过程(guchng)(guchng)如下：如下：newT第64页/共141页第六十五页，共141页。第65页/共141页第六十六页，共141页。以字符串“A!”表示(biosh) 以字符串的形式以字符串的形式(xngsh) 根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树例如(lr):ABCD以字符“!”表示A(B(! ,C(! , ! ),D(! , ! )空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以下列字符串表示第66页/共141页第六十七页，共141页。Status CreateBiTree(BiTree &T) scanf(&ch); if (ch=!) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点生成根结点(ji din) CreateBiTree(T-lchild); / 构造左子树构造左子树 CreateBiTree(T-rchild); / 构造右子树构造右子树 return OK; / CreateBiTree第67页/共141页第六十八页，共141页。 仅知二叉树的先序序列“abcdefg” 不能唯一(wi y)确定一棵二叉树，由二叉树的先序和中序序列由二叉树的先序和中序序列(xli)建树建树 如果同时(tngsh)已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根第68页/共141页第六十九页，共141页。a b c d e f gc b d a e g f例如例如(lr):(lr):aab bccddeeffggabcdefg先序序列(xli)中序序列(xli)第69页/共141页第七十页，共141页。void CrtBT(BiTree& T, char pre, char ino, int ps, int is, int n ) / 已知已知preps.ps+n-1为二叉树的先序序列为二叉树的先序序列(xli)， / insis.is+n-1为二叉树的中序序列为二叉树的中序序列(xli)，本算本算 / 法由此两个序列法由此两个序列(xli)构造二叉链表构造二叉链表 if (n=0) T=NULL; else k=Search(ino, preps); / 在中序序列在中序序列(xli)中查询中查询 if (k= -1) T=NULL; else / / CrtBT 第70页/共141页第七十一页，共141页。T=(BiTNode*)malloc(sizeof(BiTNode);T-data = preps;if (k=is) T-Lchild = NULL;else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is );if (k=is+n-1) T-Rchild = NULL;else CrtBT(T-Rchild, pre, ino, ps+(k-is)+1, k+1, n-(k-is)-1 );第71页/共141页第七十二页，共141页。第72页/共141页第七十三页，共141页。第73页/共141页第七十四页，共141页。一、何谓一、何谓(hwi)线索二叉树线索二叉树？遍历二叉树的结果(ji gu)是， 求得结点的一个线性序列。ABCDEFGHK例如(lr):先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A第74页/共141页第七十五页，共141页。指向该线性序列中的“前驱”和 “后继” 的指针(zhzhn)，称作“线索”与其相应的二叉树，称作(chn zu) “线索二叉树”包含 “线索” 的存储(cn ch)结构，称作 “线索链表”A B C D E F G H K D C B E 第75页/共141页第七十六页，共141页。对线索对线索(xin su)链表中结点的约定：链表中结点的约定： 在二叉链表的结点中增加(zngji)两个标志域，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则则Lchild域的指针指向域的指针指向(zh xin)其左子树，其左子树， 且左标志域的值为且左标志域的值为“指针指针 Link”； 否则，否则，Lchild域的指针指向域的指针指向(zh xin)其其“前驱前驱”， 且左标志的值为且左标志的值为“线索线索 Thread” 。第76页/共141页第七十七页，共141页。若该结点的右子树不空，若该结点的右子树不空，则则rchild域的指针指向域的指针指向(zh xin)其右子树，其右子树， 且右标志域的值为且右标志域的值为 “指针指针 Link”；否则，否则，rchild域的指针指向域的指针指向(zh xin)其其“后继后继”， 且右标志的值为且右标志的值为“线索线索 Thread”。 如此定义的二叉树的存储如此定义的二叉树的存储(cn ch)结结构称作构称作“线索链表线索链表”。第77页/共141页第七十八页，共141页。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右左右(zuyu)指针指针 PointerThr LTag, RTag; / 左右左右(zuyu)标志标志 BiThrNode, *BiThrTree;线索链表的类型(lixng)描述： typedef enum Link, Thread PointerThr; / Link=0:指针指针(zhzhn)，Thread=1:线索线索第78页/共141页第七十九页，共141页。二、线索二、线索(xin su)链表的遍历算法链表的遍历算法: for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而(cng r)简化了遍历的算法。第79页/共141页第八十页，共141页。例如例如(lr): 对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历中序遍历(bin l)的第一个结点的第一个结点 ？ 在中序线索化链表中结点在中序线索化链表中结点(ji din)的后继的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。第80页/共141页第八十一页，共141页。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根结点指向根结点 while (p != T) / 空树或遍历结束时，空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 第一个结点第一个结点 if ( !Visit( p-data ) ) return ERROR; while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问访问(fngwn)后继结点后继结点 p = p-rchild; / p进至其右子树根进至其右子树根 / InOrderTraverse_Thr第81页/共141页第八十二页，共141页。 在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前左、右指针域，以保存当前(dngqin)访问结访问结点的点的“前驱前驱”和和“后继后继”信息。遍历过信息。遍历过程中，附设指针程中，附设指针pre, 并始终保持指并始终保持指针针pre指向当前指向当前(dngqin)访问的、指针访问的、指针p所指所指结点的前驱。结点的前驱。三、如何三、如何(rh)建立线索链表？建立线索链表？第82页/共141页第八十三页，共141页。void InThreading(BiThrTree p) if (p) / 对以对以p为根的非空二叉树进行线索为根的非空二叉树进行线索化化 InThreading(p-lchild); / 左子树线索左子树线索化化 if (!p-lchild) / 建前驱线索建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继建后继(huj)线索线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持保持 pre 指向指向 p 的前驱的前驱 InThreading(p-rchild); / 右子树线索右子树线索化化 / if / InThreading第83页/共141页第八十四页，共141页。Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 构建中序线索链构建中序线索链表表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加添加(tin ji)头结头结点点 return OK; / InOrderThreading 第84页/共141页第八十五页，共141页。if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理处理(chl)最后一个结点最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; 第85页/共141页第八十六页，共141页。 6.6 树和森林树和森林(snln) 的表示方法的表示方法第86页/共141页第八十七页，共141页。6.6.1 树的三种存储树的三种存储(cn ch)结构结构一、双亲一、双亲(shungqn)表示法表示法二、孩子二、孩子(hi zi)链表表示法链表表示法三、三、树的二叉链表树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法第87页/共141页第八十八页，共141页。ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=6data parent一、双亲一、双亲(shungqn)表示法表示法:第88页/共141页第八十九页，共141页。 typedef struct PTNode Elem data; int parent; / 双亲(shungqn)位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结点(ji din)结构结构:C语言的类型语言的类型(lixng)描述描述:第89页/共141页第九十页，共141页。typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点根结点(ji din)的位置和结点的位置和结点(ji din)个数个数 PTree;树结构树结构:第90页/共141页第九十一页，共141页。ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 4r=0n=6 data firstchild 1 2 34 56二、孩子二、孩子(hi zi)链表表链表表示法示法:第91页/共141页第九十二页，共141页。typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子孩子(hi zi)结点结构结点结构: child nextC语言的类型语言的类型(lixng)描述描述:第92页/共141页第九十三页，共141页。 typedef struct Elem data; ChildPtr firstchild; / 孩子(hi zi)链的头指针 CTBox;双亲双亲(shungqn)结点结构结点结构 data firstchild第93页/共141页第九十四页，共141页。typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点结点(ji din)数和根结点数和根结点(ji din)的位置的位置 CTree;树结构树结构:第94页/共141页第九十五页，共141页。ABCDEFG AB C E D F Groot AB C E D F G 三、树的二叉链表三、树的二叉链表 (孩子孩子(hi zi)-兄弟）存储表示兄弟）存储表示法法第95页/共141页第九十六页，共141页。typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型语言的类型(lixng)描述描述:结点结点(ji din)结构结构: firstchild data nextsibling第96页/共141页第九十七页，共141页。 6.6.2 森林森林(snln)和二叉树的转换和二叉树的转换设森林设森林(snln) F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉树二叉树 B =( LBT, Node(root), RBT );第97页/共141页第九十八页，共141页