[ppt模板]Ch6 树和二叉树.ppt

1,知识回顾,线性表 一般的线性表 特殊的线性表：栈、队列线性表的扩展：数组、广义表特点：有序前趋、后继,2,第六章 树和二叉树,树是以分支关系定义的层次结构。树结构在客观世界广泛存在:在自然科学，如地理学领域，水系、地貌（等高线）、行政区划等都具有树结构关系；在社会人文领域，人类社会构成、组织机构等也具有树结构关系。,树型结构：非线性数据结构,4,要求,1.熟练掌握二叉树的结构特性。2.熟悉二叉树的各种存储结构的特点及适用范围。3.掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.5 赫夫曼树与其应用,主要内容,6,6.1.1 树的定义,树（tree）是n(n0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。,根,子树,树的表示法,图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子右兄弟表示法,图形表示法,西安石油大学,叶子,根,子树,嵌套集合表示法,(A(B(E(K,L),F),C(G),D(H(M),I,J)约定：根作为由子树森林组成的表的名字写在表的左边,广义表表示法,凹入表示法,又称目录表示法,左孩子右兄弟表示法,多叉树转为了二叉树,15,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm，其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,ADT Tree,16,基本操作：,查 找 类,插 入 类,删 除 类,17,Root(T)/求树的根结点,查找类：,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,RightSibling(T,cur_e)/求当前结点的右兄弟,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,TraverseTree(T,Visit()/遍历,18,InitTree(&T)/初始化置空树,插入类：,CreateTree(&T,definition)/按定义构造树,Assign(T,cur_e,value)/给当前结点赋值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,19,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,20,A,B,C,D,E,F,G,H,I,J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,例如:,21,()有确定的根；()树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,22,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),对比树型结构和线性结构的结构特点,6.1.2 基本术语,25,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,26,子孙:以某结点为根的子树中的任一结点。,A,B,C,D,E,F,G,H,I,J,M,K,L,孩子:结点的子树的根。,双亲:该结点称为孩子的双亲。,兄弟:同一个双亲的孩子之间互称兄弟。,祖先:从根到该结点所经分支上的所有结点,27,有序树：子树之间存在确定的次序关系,无序树：子树之间不存在确定的次序关系,树的深度：树中结点的最大层次,堂兄弟:其双亲在同一层的结点,结点的层次:假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,28,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟,29,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,6.2 二叉树,最简单的树二叉树,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,解决思路：,树的操作实现比较复杂。,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,二叉树:或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的特点（1）每个结点至多有二棵子树(即不存在度大于2的结点)；（2）二叉树的子树有左、右之分，且其次序不能任意颠倒。,二叉树的五种基本形态：,空树,只含根结点,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,34,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,35,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();,36,InitBiTree(,37,ClearBiTree(,38,二叉树的重要特性,39,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 层时，只有一个根结点：2i-1=20=1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。,40,性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于性质1，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。,41,性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。,证明：二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又二叉树中全部结点数nB+1(总分支数根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1,42,两类特殊的二叉树：,满二叉树：深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,43,44,完全二叉树特点：,（1）叶子结点只可能在层次最大的两层上出现;（2）对任一结点，若其右分支下子孙的最大层次为i，则其左分支下子孙的最大层次必为i或i+1。,满二叉树与完全二叉树的区别,满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原。,45,性质 4：具有 n 个结点的完全二叉树的深度为 log2n+1。x 表示=x的最大整数。,证明：设完全二叉树的深度为 k 则根据第二条性质得 2k-1(第k层第一个结点的编号）n 2k（第k1层第一个结点的编号）即 k-1 log2 n k 因为 k 只能是整数,因此,k=log2n+1。,46,证明：,设完全二叉树的深度为 k，据定义，k-1层满，k层最少1个，n=(2k-1-1)+1，根据第二条性质得 n 2k-1，因此：2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此，k=log2n+1。,47,性质 5：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2)若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,第k层上最后一个结点的编号是2k-1,它的右孩子是第k+1层上最后一个结点,编号是2k+1-1,右孩子编号是它的双亲结点编号的(2k-1)*2+1,左孩子的编号是(2k-1)*2所以，编号为 i 的结点的左孩子结点编号是2i，右孩子结点编号是2i+1,双亲结点编号i/2,49,问 题,具有n个结点的非空二叉树的最小深度是多少？最大深度是多少？,答1：当是满二叉树时深度最小。,最小深度：log2n+1,当每个节点都只有左（右）子树时深度最大,最大深度：n,50,思考题,1.具有n个结点的完全二叉树中有多少个叶子结点？有多少个度为2的结点？2.具有n0个叶子结点的完全二叉树中共有多少个结点？,51,二叉树的存储结构,二、二叉树的链式 存储表示,一、二叉树的顺序 存储表示,存储方式：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。,一、二叉树的顺序存储结构,/-二叉树的顺序存储表示-#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;,例如:,A,B,C,D,E,F,A B D 0 C 0 E 0 0 0 0 0 0 F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,0表示不存在此结点,完全二叉树的数组表示 一般二叉树的数组表示,55,特点：结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树（在最坏情况下，深度为k且只有k个结点的单支树需要长度为2k-1的一维数组）。由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,二、二叉树的链式存储结构,（1）二叉链表,（2）三叉链表,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1.二叉链表,F,在n个结点的二叉链表中，有n+1个空指针域,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:,A,D,E,B,C,F,root,2三叉链表,parent lchild data rchild,结点结构:,F,typedef struct TriTNode/结点结构 TElemType data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;/双亲指针 TriTNode,*TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,二叉链存储结构的二叉树操作实现,在二叉链存储结构下，针对一棵二叉树，主要涉及如下几个功能模块：二叉树的初始化操作；二叉树中给某结点插入一个左结点的操作；二叉树中给某结点插入一个右结点的操作；删除二叉树中某结点的左子树操作；删除二叉树中某结点的右子树操作。各算法的基本思想及程序实现如下：typedef struct Node DataType data;struct Node*leftChild;struct Node*rightChild;BiTreeNode;/*结点的结构体定义*/,1.二叉树的初始化 算法的基本思想:创建二叉树的头结点。程序实现：void Initiate(BiTreeNode*root)*root=(BiTreeNode*)malloc(sizeof(BiTreeNode);(*root)-leftChild=NULL;(*root)-rightChild=NULL;,2.二叉树中给某结点插入一个左结点的操作,算法的基本思想:若当前结点(假设为curr）非空，在curr的左子树插入元素值为x的新结点，原curr所指结点的左子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回空指针。,程序实现：BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataType x)BiTreeNode*s,*t;if(curr=NULL)return NULL;t=curr-leftChild;s=(BiTreeNode*)malloc(sizeof(BiTreeNode);s-data=x;s-leftChild=t;s-rightChild=NULL;curr-leftChild=s;return curr-leftChild;,3.删除二叉树中某结点的左子树操作,算法的基本思想:若curr非空，删除curr所指结点的左子树。若删除成功，返回删除结点的双亲结点指针，否则返回空指针。程序实现：BiTreeNode*DeleteLeftTree(BiTreeNode*curr)if(curr=NULL|curr-leftChild=NULL)return NULL;Destroy(,66,知识回顾,树和二叉树的定义二叉树的特点二叉树的存储结构,67,6.3.1二叉树的遍历,68,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,69,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结点的信息等。,70,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,71,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。,72,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,73,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先（根）序的遍历算法：,74,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。,中（根）序的遍历算法：,75,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后（根）序的遍历算法：,76,T L R,先序遍历序列：A B D C,先序遍历:,77,L T R,中序遍历序列：B D A C,中序遍历:,78,L R T,后序遍历序列：D B C A,后序遍历:,79,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,80,三、算法的递归描述,void InorderTraverse(BiTree T,Status(*visit)(TElemType e)/中序遍历二叉树 if(T)InorderTraverse(T-lchild,visit);/中序遍历左子树 visit(T-data)/访问根结点 InorderTraverse(T-rchild,visit);/中序遍历右子树,见演示,81,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S);Push(S,T);/根指针进栈While(!StackEmpty(S)While(GetTop(S,p)/InOrderTraverse,算法1,四、中序遍历算法的非递归描述,82,-,*,a,null,null,b,null,null,c,null,null,中序遍历序列:a*b-c,While(!StackEmpty(S)While(GetTop(S,p)/if,83,status InorderTraverse(BiTree T,status(*Visit)(TelemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/根指针进栈,遍历左子树 else/根指针退栈,访问根结点,遍历右子树 Pop(S,p);Visit(p-data);p=p-rchild;/else/while Return OK;/InorderTraverse,算法2,中序遍历算法的非递归描述,84,p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/根指针进栈,遍历左子树 else/根指针退栈,访问根结点,遍历右子树 Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;/else/while,-,*,a,b,c,85,先序遍历结果+*/A B C D E前缀表示法中序遍历结果A/B*C*D+E中缀表示法后序遍历结果A B/C*D*E+后缀表示法层次遍历结果+*E*D/C A B,用二叉树表示算术表达式,层序遍历,层序遍历二叉树算法的框架是若二叉树为空，则空操作；否则，如队列不空，循环：根结点入队，并作为当前结点；将当前结点的左右孩子入队；做出队操作，队首元素作为当 前结点最后，出队序列就是层序遍历 序列遍历结果-+/a*e f b-c d,void LayerOrder(Bitree T)/层序遍历二叉树 if(T)InitQueue(Q);/建一个空队（初始化队列）EnQueue(Q,T);/将一个结点插入队尾的函数 while(!QueueEmpty(Q)DeQueue(Q,/p的右孩子入队/LayerOrder,层次遍历算法(需要利用队列),当孩子为空时不要将空指针入队,遍历算法思想的应用-步骤,要明确所要编写的算法的功能描述（包括所涉及的各参数或变量的含义）这在递归算法中尤其要注意。在此基础上按如下步骤讨论算法的实现：如果T为空，则按预定功能实现对空树的操作，以满足功能要求（包括对相应参数，变量的操作）。否则，假设算法对T的左右子树都能分别实现预定功能，在此基础上，通过按预定要求适当调用对左右子树的算法的功能，及对当前结点的操作实现对整个二叉树的功能（包括对各变量、参数的操作）。,89,例1：统计二叉树中叶子结点的个数.(先序遍历),90,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,91,void CountLeaf(BiTree T,int/if/CountLeaf,92,例2：求二叉树的深度(后序遍历),93,算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,94,int Depth(BiTree T)/返回二叉树的深度 if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;,95,例3：建立二叉树的存储结构,96,以字符串的形式 根 左子树 右子树定义一棵二叉树,例如:,A,B,C,D,以空白字符“”表示,A(B(,C(,),D(,),空树,只含一个根结点的二叉树,A,以字符串“A”表示,以下列字符串表示,97,Status CreateBiTree(BiTree/CreateBiTree,98,A B C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,Status CreateBiTree(BiTree,99,问题,已知一棵二叉树的先序遍历序列，能否得到这棵树？,100,例：一棵树的先序序列为：1，2，3。请画出这棵树。,101,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。,前序序列：1，2，3，4，5，6，7，8，9 中序序列a：3，2，5，4，1，6，8，7，9 中序序列b：4，3，5，2，1，7，6，8，9,可以证明：一棵二叉树的先序序列和中序序列可以唯一的确定这棵二叉树。,结论 仅已知一棵二叉树的先序遍历序列，不能唯一确定这棵树。,由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例,先序序列 ABHFDECKG 和中序序列 HBDFAEKCG,构造二叉树过程如下：,已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。,分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,105,106,二叉树的遍历：以一定的次序排列二叉树的结点。-非线性结构的线性化。传统的二叉链表存储结构只存储了结点的左右孩子的信息，没有存储其前趋和后继信息。这些信息只有在遍历过程中才能得到。传统的二叉树遍历方法：-利用堆栈 效率低,知识回顾,107,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,108,问题：能否在遍历过程中把结点的前趋和后继信息保存下来，并且提高算法的效率呢？,109,6.3.2线索二叉树Threaded Binary Tree,110,主要内容（1）什么是线索二叉树（2）基于线索二叉树的遍历方法（3）如何建立线索二叉树,111,线索二叉树的引入和定义,所以，空指针数目2n(n-1)=n+1个。,证明：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域。,除根结点外，二叉树中每一个结点有且仅有一个双亲，即每个结点地址占用了双亲的一个直接后继，n个结点地址共占用了n-1个双亲的指针域。也就是说，只会有n1个结点的链域存放指针。,用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。,112,A,D,E,B,C,F,root,lchild data rchild,结点结构:,F,113,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,这就是线索二叉树（Threaded Binary Tree）,对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。,讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？,先定义遍历规则，然后才能定义直接前驱和后继。,115,讨论2：如何获得这种“直接前驱”或“直接后继”？有何意义？,二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。,每个结点增加两个域：fwd和bwd；,存放前驱指针,存放后继指针,如何预存这类信息？,与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。,缺点：空间效率太低！,问题：计算机如何判断是孩子指针还是线索指针？,如何区别？,约定:,当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,为区别两种不同情况，特增加两个标志域：,1.有关线索二叉树的几个术语,线索链表：线 索：线索二叉树：线 索 化：,用含Tag的结点样式所构成的二叉链表。指向结点前驱和后继的指针。在二叉树的结点上加上线索的二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程。,线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针仍然指向孩子结点（称为“正常情况”）,119,typedef struct BiThrNod TElemType data;struct BiThrNode*lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;,typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索,二叉树的二叉线索存储表示,在二叉树的线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。,采用中序遍历方法时的约定,121,头结点：Ltag=0,lchild指向根结点rtag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点,中序序列：BCAED,122,线索链表的遍历算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,123,例如:对中序线索化链表的遍历算法,中序遍历的第一个结点？,在中序线索化链表中结点的后继？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,124,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;/第1个结点 Visit(p-data);while(p-RTag=Thread/p进至其右子树根/InOrderTraverse_Thr,125,p=T-lchild;/T指向头结点，p指向根结点 while(p!=T)/空树或遍历结束时p=T，p指向头结点 while(p-LTag=Link)p=p-lchild;visit(p-data);/访问左子树为空的结点 while(p-RTag=Thread,输出:B C A E D,126,A,G,E,I,D,J,H,C,F,B,例1：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。,A,Tag=1表示线索:Ltag=1表示前驱Rtag=1表示后继,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。引入一个指针pre,始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。,如何进行二叉树的线索化？,128,悬空？NIL,悬空？NIL,解：对该二叉树中序遍历的结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例2：画出以下二叉树对应的中序线索二叉树。,线索二叉树的生成线索化,线索化过程就是在遍历过程中修改空指针的过程,129,注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G,对应的中序线索二叉树存储结构如图所示：,130,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。引入一个指针pre,始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。,131,void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThreading(p-rchild);/右子树线索化/if/InThreading,132,Status InOrderThreading(BiThrTree/InOrderThreading,133,if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;,例3：给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。,6.4 树和森林,136,主要内容,树与二叉树的转换森林与二叉树的转换树与森林的遍历,137,树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,138,一、双亲表示法:,实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置,139,A,B,C,D,E,F,G,0 A-11 B 02 C 03 D 04 E 2 5 F 26 G 5,n=7,data parent,一、双亲表示法:,140,typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;,data parent,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,141,typedef struct PTNode nodes MAX_TREE_SIZE;int n;/结点个数 PTree;,树结构:,特点：找双亲容易，找孩子难,142,A,B,C,D,E,F,G,0 A 1 B 2 C 3 D 4 E 5 F 6 G,r=0n=7,data firstchild,1 2 3,4 5,6,二、孩子链表表示法:,-1000224,143,typedef struct CTNode int child;struct CTNode*next;*ChildPtr;,孩子结点结构:,child next,C语言的类型描述:,144,typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;,双亲结点结构,data firstchild,145,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,树结构:,146,A,B,C,D,E,F,G,AB C E D F G,root,AB C E D F G,三、树的二叉链表(孩子-兄弟）存储表示法,147,typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,结点结构:,firstchild data nextsibling,148,树与二叉树转换,树与二叉树转换,150,将树转换成二叉树,加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,152,将二叉树转换成树,加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,森林和二叉树的转换,设森林 F=(T1,T2,Tn);T1=(root,t11,t12,t1m);,二叉树 B=(LBT,Node(root),RBT);,由森林转换成二叉树的转换规则为:,若 F=，则 B=；否则，由 ROOT(T1)对应得到 Node(root)；由(t11,t12,t1m)对应得到 LBT；由(T2,T3,Tn)对应得到 RBT。,由二叉树转换为森林的转换规则为：,若 B=，则 F=；否则，由 Node(root)对应得到 ROOT(T1)；由LBT 对应得到(t11,t12,t1m)；由RBT 对应得到(T2,T3,Tn)。,森林转换成二叉树将各棵树分别转换成二叉树将每棵