《第六章01(ldq)3.ppt》由会员分享，可在线阅读，更多相关《第六章01(ldq)3.ppt（129页珍藏版）》请在三一办公上搜索。
1、数 据 结 构 C语言描述,青海师范大学计算机学院,DATA STRUCTURE Specification on C,数据结构 线性结构：线性表、栈、队列、串 非线性结构：至少存在一个数据元素有不止一个直接前驱或后继（树或图等）,第六章 树和二叉树,6.1 树的定义与基本术语,1,树的基本概念,树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根(root)的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为这个根结点的子树(subTree)。每棵子树的根结点有且仅有一
2、个直接前驱，但可以有0个或多个直接后继。,树的定义是采用递归方法,A,n=1的树,n1的树,T1,T2,T3,(a)一棵树结构(b)一个非树结构(c)一个非树结构,A（B（D，E（H，I），F），C（G）,（2）文氏图表示法,（3）广义表表示法,2,树的图解表示法,（1）树型表示法,（4）凹入表示法,结点：包含一个数据元素及若干指向其他结点的分支信息。结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。,3,树的相关术语,叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。,孩子、双亲：一个结点的直接后继称为该结点的孩子结点；一个结点的直接前驱称为该
3、结点的双亲结点。兄弟：具有同一个双亲的孩子结点互称为兄弟。,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,路径：如果树的结点序列n1,n2,nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1,n2,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,有序树、无序树：如果一棵树中结点的各子树从
4、左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,森林：m(m0)棵互不相交的树的集合。,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,ADT Tree 数据对象D：具有相同的特性数据元素的集合。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R=H，H是如下的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关
5、系H下没有前驱。(2)除root以外，D中每个结点在关系H下都有且仅有一个前驱。,4,树的抽象数据类型表示,基本操作P：(1)InitTree（&T）:将T初始化为一棵空树。(2)DestoryTree（&T）:销毁树T。CreateTree（&T）:创建树T。TreeEmpty（T）:若T为空,则返回TRUE,否则返回FALSE。(5)TreeDepth(T):树T存在，返回T的深度。Root（T）：返回树T的根。Value(T,cur_e):树T存在，返回树T中结点cur_e的值。(8)Parent（T，cur_e）：树T存在，cur_e是T中非根结点，则返回它的双亲，否则返回“空”。(9
6、)LeftChild（T，cur_e）：树T存在，cur_e是T中的非叶子结点，则返回它的最左孩子，否则返回“空”。,(10)Assign(T,cur_e,value)：树T存在，cur_e是T中的某个结点。结点cur_e赋值为value。(11)RightSibling(T,cur_e):树T存在，cur_e是T中的某个结点，若cur_e有有兄弟，则返回它的有兄弟，否则返回空值。(12)InsertChild（&T，&p，i，c）：树T存在，p指向T中某个结点，非空树c与T不相交。将c插入T中，做p所指向结点的第i棵子树。(13)DeleteChild（&T，&p，i）：树T存在，p指向T中
7、某个结点，1id，d为p所指向结点的度。删除T中p所指向结点的第i棵子树。(14)TraverseT（T，Visit（）：树T存在，Visit（）是对结点操作的应用函数。按照某种次序对树T的每个结点调用Visit（）函数访问一次且最多一次。若Visit（）失败，则操作失败。,6.2 二叉树,1,定义及基本形态,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。特点：每个结点最多有两棵子树；二叉树是有序的，其次序不能任意颠倒。,T=,n=0 r,TL,TR,n0,二叉树的基本形态：,(1)Initi
8、ate（bt）：将bt初始化为空二叉树。(2)Create(bt)：创建一棵非空二叉树bt。(3)Destory（bt）：销毁二叉树bt。(4)Empty（bt）：若bt为空，则返回TRUE，否则返回FALSE。(5)Root(bt)：求二叉树bt的根结点。若bt为空二叉树，则函数返回“空”。(6)Parent（bt，x）：求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉树的根结点或二叉树bt中无结点x，则返回“空”。,2,二叉树的基本操作,(7)LeftChild（bt，x）：求左孩子。若结点x为叶子结点或x不在bt中，则返回“空”。(8)RightChild（bt，x）：求右孩子
9、。若结点x为叶子结点或x不在bt中，则返回“空”。(9)Traverse（bt）:遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。(10)Clear（bt）：清除操作。将二叉树bt置为空树。,（1）斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树。,在斜树中，每一层只有一个结点；斜树的结点个数与其深度相同。,斜树的特点：,3,特殊的二叉树,（2）满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,不是满二叉树，虽然所
10、有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多；满二叉树在同样深度的二叉树中叶子结点个数最多,（3）完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；完全二叉树中如果有度为1的结点，只
11、可能有一个，且该结点只有左孩子；深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。,证明：当i=1时，第1层只有一个根结点，而 2i-1=20=1，结论显然成立。假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点，则 i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。,4,二叉树的基本性质,性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1
12、可知，深度为k的二叉树中结点个数最多=2k-1；每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21。,证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：nn12n21 因此可以得到：n0n21。,性质5-4 具有n个结点的完全二叉树的深度为 log2n+1。,证明：假设具有n个结点的完全二叉树的
13、深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,最少结点数,最多结点数,对不等式取对数，有：k-1log2nk即：log2nklog2n+1由于k是整数，故必有k log2n+1。,性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点i），有：（1）如果i1，则结点i的双亲结点的序号为 i/2；如果i1，则结点i是根结点，无双亲结点；（2）如果2in，则结点i的左孩子的序号为2i；如果2in，则结点i无左孩子；（3）如果2i1n，则结点i的右孩子的序号为2i1；如果2i1n，则结点 i无右孩子。,对一棵具有n个
14、结点的完全二叉树中从1开始按层序编号，则：结点i的双亲结点为 i/2；结点i的左孩子为2i；结点i的右孩子为2i1。,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,完全二叉树的基本性质：,二叉树的结构是非线性的，每一结点最多可有两个后继。二叉树的存储结构有两种：顺序存储结构和链式存储结构。,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。,（一）顺序存储结构,5,二叉树的存储结构,以编号为下
15、标,（1）完全二叉树的顺序存储,以编号为下标,按完全二叉树编号,（2）一般二叉树的顺序存储,（3）斜树的顺序存储,深度为k的右斜树，k个结点需分配2k1个存储单元。,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,二叉树的顺序存储结构一般仅存储完全二叉树,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,（二）链式存储结构,Typedef struct Node DataType data;struct Node*LChild;struct Node*RChild;BiTNode,*B
16、iTree;,C语言定义：,（1）二叉链表,具有n个结点的二叉链表中，有多少个空指针？,二叉树和对应的二叉链表：,n+1个空指针，2n个指针域,基本思想：为了便于找到双亲结点，在二叉链表的基础上增加了一个指向双亲的指针域。,其中：data、lchild和rchild三个域的含义 同二叉链表的结点结构；parent域为指向该结点的双亲结点的指针。,（2）三叉链表,结点结构：,二叉树和对应的三叉链表：,二叉树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。,如何理解访问?,抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。,如何理解次序?,树
17、通常有先序（根）遍历、中序（根）遍历和后序（根）遍历三种方式。,树结构（非线性结构）线性结构。,遍历的实质?,6.3 二叉树的遍历,1,二叉树遍历概述,二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种：先序：DLR中序：LDR后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,先序（若二叉树为空，则空操作返回；否则：访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树。,-,+,a,*,-,b,c,d,/,e,f,（1）先序遍历(Preorder Traversal),若二叉树为空，则空操作返回；否则：中序遍历根结点的左
18、子树；访问根结点；中序遍历根结点的右子树。,-,+,/,-,e,f,d,c,b,a,（2）中序遍历(Inorder Traversal),若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树；访问根结点。,-,+,a,*,-,b,c,d,/,e,f,（3）后序遍历(Postorder Traversal),（1）先序遍历,void PreOrder(BiTree root)/*先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)Visit(root-data);/*访问根结点*/PreOrder(root-LChild);/
19、*先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树*/,2,二叉树的递归遍历算法,void InOrder(BiTree root)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)InOrder(root-LChild);/*中序遍历左子树*/Visit(root-data);/*访问根结点*/InOrder(root-RChild);/*中序遍历右子树*/,（2）中序遍历,图：中序遍历二叉树的递归过程,void PostOrder(BiTree root)/*后序遍历二叉树，root为指向二叉树(或某一子树)根
20、结点的指针*/if(root!=NULL)PostOrder(root-LChild);/*后序遍历左子树*/PostOrder(root-RChild);/*后序遍历右子树*/Visit(root-data);/*访问根结点*/,（3）后序遍历,作业：,算法作业：深入理解二叉树遍历的三种方法。先序、中序、后序遍历。书面作业P194(1)(2),（1）输出二叉树中的结点（2）输出二叉树中的叶子结点（3）统计叶子结点数目（4）建立二叉链表方式存储的二叉树（5）求二叉树的高度（6）按树状打印二叉树以上操作可以通过对二叉树遍历来完成，一方面要重点理解访问根节点操作的含义，另一方面要注意对具体的实现时
21、是否要考虑遍历的次序选择的要求。,3,遍历算法应用,（1）输出二叉树中的结点 遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的结点并无次序要求，因此可用三种遍历中的任何一种算法完成。,void PreOrder(BiTree root)/*先序遍历输出二叉树结点,root为指向二叉树根结点的指针*/if(root!=NULL)printf(root-data);/*输出根结点*/PreOrder(root-LChild);/*先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树*/,（2）输出二叉树中的叶子结点 输出二叉树中的叶子结点与输出二叉树中的结点相比，它
22、是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否有满足叶子结点的条件，如果满足则进行输出。,void PreOrder(BiTree root)/*先序遍历输出二叉树中的叶子结点,root为指向二叉树根结点的指针*/if(root!=NULL)if(root-LChild=NULL/*先序遍历右子树*/,（3）统计叶子结点数目,方法一：统计二叉树中的叶子节点数目并无次序要求，因此可用三种遍历算法的任何一种完成，只需将访问操作具体变为判断是否为叶子节点，如果是叶子节点，则进行统计即可。/*LeafCount是保存叶子结点数目的全局变量,调用之前初始化值为0*/void l
23、eaf(BiTree root)if(root!=NULL)leaf(root-LChild);leaf(root-RChild);if(root-LChild=NULL,方法二：采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左、右子树的叶子结点数之和。int leaf(BiTree root)int LeafCount;if(root=NULL)LeafCount=0;else if(root-lchild=NULL),（4）建立二叉链表方式存储的二叉树 给定一棵二叉树，可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，也可以创建相应的二叉链表。这里所说的遍历序列是
24、一种“扩展的遍历序列”。在通常的遍历序列中，均忽略空子树，而在扩展的遍历序列中，必须用特定的元素表示空子树。例如，下面左图中二叉树的“扩展先序遍历序列”如右图所示（其中用小圆点表示空子树）：,AB.DF.G.C.E.H.,A,E,B,C,D,1,2,G,F,ABC DE G F,空格代表不存在的左、右子树,建立二叉树的二叉链表过程：(按先序序列)按下列次序读入字符:,用“扩展先序遍历序列”创建二叉链表:void CreateBiTree(BiTree*bt)char ch;scanf(,二叉树建立的演示,设函数表示二叉树bt的高度，则递归定义如下:若bt为空，则高度为0；若bt非空，其高度应为
25、其左右子树高度的最大值加1，如下图所示。二叉树的高度(深度)为二叉树中结点层次的最大值，即结点的层次自根结点起递推。设根结点为第1层的结点，所有h层的结点的左右孩子结点在h+1层，则可以通过先序遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的高度。,（5）求二叉树的高度,int PostTreeDepth(BiTree bt)/*后序遍历求二叉树的高度递归算法*/int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt-LChild);/*求左子树的深度*/hr=PostTreeDepth(bt-RChild);/*求右子树的深度*/max=hlhr?
26、hl:hr;/*得到左、右子树深度较大者*/return(max+1);/*返回树的深度*/else return(0);/*如果是空树，则返回0*/,（6）按树状打印的二叉树 例：假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母,要求实现如下图所示打印结果。这实际是一个二叉树的横向显示问题：因为二叉树的横向显示应是二叉树竖向显示的90旋转，又由于二叉树的横向显示算法一定是中序遍历算法，所以把横向显示的二叉树算法改为先右子树再根结点再左子树的RDL结构，实现算法如下：,void PrintTree(TreeNode Boot,int nLayer)/*按竖向树状打印的二叉树*/if
27、(Boot=NULL)return;PrintTree(Boot-pRight,nLayer+1);for(int i=0;ich);PrintTree(Boot-pLeft,nLayer+1);,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?（见下图）,4,由遍历序列确定二叉树,根据前序序列的第一个元素建立根结点；在中序序列中找到该元素，确定根结点的左右子树的中序序列；在前序序列中确定左右子树的前序序列；由左子树的前序序列和中序序列建立左子树；由右
28、子树的前序序列和中序序列建立右子树。,已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：,前序：A B C D E F G H I中序：B C A E D G H F I,前序：B C中序：B C,前序：D E F G H I中序：E D G H F I,前序：F G H I中序：G H F I,前序：D E F G H I中序：E D G H F I,（1）前序遍历算法的执行轨迹,5,基于栈的递归消除,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,A,D,B,C,访问结点序列:,A,栈S内容:,B,D,A,A,D,B,C,D,访问结点序列:,A,栈S内容:,
29、B,D,C,A,D,B,C,C,（2）中序遍历二叉树的非递归算法【算法思想】P取二叉树根 While(P|栈不空)P向左前进直至不再有左子女，途经结点进栈；若栈不空，出栈一个元素至P；访问P；P前进至右子女；【递归过程】,【算法实现1】中序遍历二叉树的非递归算法（直接实现栈操作）/*sm 表示栈，top表示栈顶指针*/void inorder(BiTree root)/*中序遍历二叉树，bt为二叉树的根结点*/top=0;p=bt;do do while(p!=NULL)if(topm)return(overflow);top=top+1;stop=p;p=p-LChild;/*遍历左子树*/
30、if(top!=0)p=stop;top=top-1;Visit(p-data);/*访问根结点*/p=p-RChild;/*遍历右子树*/while(p!=NULL|top!=0),【算法实现2】中序遍历二叉树的非递归算法（调用栈操作的函数）void InOrder（BiTree root）/*中序遍历二叉树的非递归算法*/InitStack(,（3）后序遍历二叉树的非递归算法【算法设计】判断刚访问过的结点q是不是当前栈顶结点p的右孩子 p无右孩子，此时应该访问根结点；如p的右孩子是刚被访问过的结点q（表明p的右子树已遍历过），此时也应该访问根结点。除这两种情况外，均不应访问根，而是要继续进
31、入右子树中。【算法思想】从根结点开始，只要当前结点存在，或者栈不空，则重复下面的步骤：从当前结点开始，进栈并走左子树，直到左子树为空；如果栈顶结点的右子树为空，或者栈顶结点的右孩子为刚访问过的结点，则退栈并访问，然后将当前结点指针置空；否则，走右子树。,【算法描述】void PostOrder（BiTree root）BiTNode*p,*q；BiTNode*S；int top=0;q=NULL;p=root;S=（BiTNode*）malloc（sizeof（BiTNode*）*NUM）;/*NUM为预定义的常数*/while(p!=NULL|top!KG-*2=0),while(p!=NU
32、LL)top=+;stop=p;p=p-LChild;/*遍历左子树*/if(top0)p=stop;if(p-RChild=NULL)|(p-RChild=q)/*无右孩子，或右孩子已遍历过*/visit(p-data);/*访问根结点*/q=p;/*保存到q，为下一次已处理结点前驱*/top-;p=NULL;else p=p-RChild;free(s);,（1）问题：如何保存二叉树的遍历运算的结果？或如何得到二叉树中结点在遍历序列中的前驱和后继信息？（2）方法：A、将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；B、充分利用二叉链表中的空链域，将遍历过程中
33、结点的前驱、后继信息保存下来。具体办法：若结点有左子树，则其LChild域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其RChild域指向其右孩子，否则RChild域指向其后继结点。为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下所示：,6.4 线索二叉树,1,基本概念,其中：,线索：指向前驱和后继结点的指针叫做线索；线索链表：以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表；线索化：对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化；线索二叉树：线索化了的二叉树称为线索二叉树。,（3）概念：,（1）线索化二叉树的实质：将二叉链表中的空指针域
34、填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此，线索化的过程即为在遍历过程中修改空指针域的过程。（2）线索化二叉树的方式：对于同一棵二叉树按照不同的次序进行线索化，可以得到不同的线索二叉树，包括先序、中序和后序线索二叉树。,2,二叉树的线索化,（3）中序线索化二叉树的算法：中序线索化采用中序递归遍历算法框架 加线索操作就是访问结点操作 加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一个指针pre，始终记录刚访问过的结点，其操作如下：如果当前遍历结点root的左子域为空，则让左子域指向pre 如果前驱pre的右子域为空，则让右子域指向当前
35、遍历结点root 为下次做准备，当前访问结点root作为下一个访问结点的前驱pre,void Inthread(BiTree root)if(root!=NULL)Inthread(root-LChild);/*线索化左子树*/if(root-LChild=NULL)root-Ltag=1;root-LChild=pre;/*置前驱线索*/if(pre!=NULL/*线索化右子树*/,（4）中序线索化二叉树动态演示,（1）找结点的中序前驱结点 分析：根据线索二叉树的基本概念和存储结构可知，对于结点p，当p-Ltag=1时，p-LChild指向p的前驱；当p-Ltag=0时，p-LChild指向
36、p的左孩子。由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。,3,找前驱、后继结点 在中序线索二叉树中,查找算法：void InPre(BiTNode*p,BiTNode*pre)/*在中序线索二叉树中查找p的中序前驱,并用pre指针返回结果*/if(p-Ltag=1)pre=p-LChild;/*直接利用线索*/else/*在p的左子树中查找“最右下端”结点*/for(q=p-LChild;q-Rtag=0;q=q-RChild);pre=q;,找结点的中序前驱结点动态演示：,（2）找结点的中序后继结点 分析：对于结点p，若要
37、找其后继结点，当p-Rtag=1时，p-RChild即为p的后继结点；当p-Rtag=0时，说明p有右子树，此时p的中序后继结点即为其右子树的“最左下端”的结点。,查找算法：void InSucc(BiTNode*p,BiTNode*succ)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/if(p-Rtag=1)succ=p-RChild;/*直接利用线索*/else/*在p的右子树中查找“最左下端”结点*/for(q=p-RChild;q-Ltag=0;q=q-LChild);succ=q;,找结点的中序后继结点动态演示：,遍历线索树的问题可以分为两步：第一步是求出
38、某种遍历次序下第一个被访问结点，然后连续求出刚访问结点的后继结点，直至所有的结点均被访问。（1）在中序线索树上求中序遍历的第一个结点 BiTNode*InFirst(BiTree Bt)BiTNode*p=Bt;if(!P)return(Null)While(p-LTag=0)p=p-LChild;return p,4,遍历中序线索树,（2）遍历中序二叉线索树 void TInOrder(BiTree Bt)BiTNode*p;P=InFirst(Bt);While(p)Visit(p);p=InNext(p);通过调用InFirst和 InNext，可以实现对中序线索树的中序遍历，且不需要使
39、用递归栈。,（1）插入结点运算 在中序线索二叉树上插入新结点可分两种情况：要么作某结点的左孩子、要么作某结点的右孩子。在后种情况中，用InsNode(BiTNode*p,BiTNode*r)表示在线索二叉树中插入r所指向的结点，做p所指结点的右孩子。此时有两种情况：若结点p的右孩子为空，则插入结点r的过程很简单。原来p的后继变为r的后继，结点p变为r的前驱，结点r成为p的右孩子，结点r的插入对p原来的后继结点没有任何的影响。插入过程如下图所示。,5,插入、删除运算 以中序线索二叉树为例,图：结点的右孩子为空时的插入操作,若p的右孩子不为空，则插入后，p的右孩子变为r的右孩子结点，p变为r的前驱
40、结点，r变为p的右孩子结点，这时还需要修改原来p的右子树中“最左下端”结点的左指针域，使它由原来的指向结点p变为指向结点r。插入过程如下图所示。,图：结点的右孩子非空时的插入操作,算法描述：void InsNode(BiTNode*p,BiTNode*r)if(p-Rtag=1)/*p无右孩子*/r-RChild=p-RChild;/*p的后继变为r的后继*/r-Rtag=1;p-RChild=r;/*r成为p的右孩子*/r-LChild=p;/*p变为r的前驱*/r-Ltag=1;Else/*p有右孩子*/s=p-RChild;while(s-Ltag=0)s=s-LChild;/*查找p结
41、点的右子树的“最左下端”结点*/r-RChild=p-RChild;/*p的右孩子变为r的右孩子*/r-Rtag=0;r-LChild=p;/*p变为r的前驱*/r-Ltag=1;p-RChild=r;/*r变为p的右孩子*/s-LChild=r;/*r变为p原来右子树的“最左下端”结点的前驱*/,（2）删除结点运算,图：删除线索二叉树中结点的过程,6.5 树、森林和二叉树的关系,（1）双亲表示法 用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下：,数据,双亲,1,树的存储结构,data：存储树中结点的数据信息parent：存储
42、该结点的双亲在数组中的下标,双亲表示法的形式说明如下：define MAX 100typedef struct TNode DataType data;int parent;TNode;一棵树可以定义为:typedef struct TNode treeMAX;int nodenum;/*结点数*/ParentTree;,下标 data parent,如何查找双亲结点？时间性能？,如何查找孩子结点？时间性能？,下标 data parent,firstchild,下标 data parent,rightsib,如何查找兄弟结点？时间性能？,（2）孩子表示法 方法：把每个结点的孩子结点排列起来，构
43、成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。,存储结构定义如下：typedef struct ChildNode/*孩子链表结点的定义*/int Child;/*该孩子结点在线性表中的位置*/struct ChildNode*next;/*指向下一个孩子结点的指针*/ChildNode;typedef struct/*顺序表结点的结构定义*/DataType data;/*结点的信息*/ChildNode*FirstChild;/*指向孩子链表的头指针*/DataNode;typedef struct
44、/*树的定义*/DataNode nodesMAX;/*顺序表*/int root,num;/*该树的根结点在线性表中的位置和该树的结点个数*/ChildTree;,012345678,下标 data firstchild,A B C D E F G H I,如何查找孩子结点？时间性能？,A B C D E F G H I,012345678,下标 data firstchild,如何查找双亲结点？时间性能？,结点结构：,data：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。,存储结构定义：,typedef
45、 struct CSNode DataType data;/*结点信息*/Struct CSNode*FirstChild,*Nextsibling;/*第一个孩子,下一个兄弟*/CSNode,*CSTree;,（3）孩子兄弟表示法,如何查找兄弟结点？时间性能？,如何查找孩子结点？时间性能？,是哪些树结构的存储结构?,树和二叉树之间具有对应关系,（1）树转换为二叉树,2,树、森林与二叉树的相互转换,树和二叉树之间的对应关系：树：兄弟关系二叉树：双亲和右孩子 树：双亲和长子二叉树：双亲和左孩子,转换方法：加线树中所有相邻兄弟之间加一条连线。去线对树中的每个结点，只保留它与第一个孩子结点之间的连线
46、，删去它与其它孩子结点之间的连线。层次调整以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。,1.兄弟加线.,转换分解图如下：,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,3.顺时针转动,使之层次分明.,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,A,B,C,D,E,F,G,3.顺时针转动,使之层次分明.,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,树与二叉树的对应,（2）森林转换为二叉树 转换方法 将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉
47、树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。递归定义 将森林F看作树的有序集F=T1，T2，,TN，它对应的二叉树为B（F）：若N=0，则B（F）为空；若N0，二叉树B（F）的根为森林中第一棵树T1的根；B（F）的左子树为B（T11，T1m），其中T11，T1m是T1的子树森林；B（F）的右子树是B（T2，TN）。,（3）二叉树还原为树或森林 还原方法加线若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、，都与结点y用线连起来；去线删去原二叉树中所有的双亲结点与右孩子结点的连线；层次调整整理由、两步所得到的树或森林，使之层次分明。递归定义 若B是一棵二叉树，T是B
48、的根结点，L是B的左子树，R为B的右子树，且B对应的森林F（B）中含有的n棵树为T1,T2,Tn，则有：B为空，则F（B）为空的森林（n0）；B非空，则F（B）中第一棵树T1的根为二叉树B的根T；T1中根结点的子树森林由B的左子树L转换而成，即F（L）=T11,T1m；B的右子树R转换为F（B）中其余树组成的森林，即F(R)T2,T3,Tn。,（1）树的遍历 先根遍历 若树非空，则遍历方法为：访问根结点；从左到右，依次先根遍历根结点的每一棵子树。后根遍历 若树非空，则遍历方法为：从左到右，依次后根遍历根结点的每一棵子树；访问根结点。,3,树与森林的遍历,ABEFCDG,ABEFCDG,树的先根遍历等价于二叉树的先序遍历！,EFBCGDA,EFBCGDA,树的后序遍历等价于二叉树的中序遍历！,（2）森林的遍历 森林的遍历方法主要有以下三种：先序遍历 若森林非空，则遍历方法为：访问森林中第一棵树的根结点；先序遍历第一棵树的根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历 若森林非空，则遍历方法为：中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。后序遍历 若森林非空，则遍历方法为：后序遍历森林中第一棵树的根结点的子树森林；后序遍历除去第一棵树之后剩余的树构成的森林；访问第一棵树的根结点。,
