《第6章树和二叉树n.ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树n.ppt（200页珍藏版）》请在三一办公上搜索。
1、第六章树和二叉树,学习目标 掌握树的定义、表示方法、基本性质、存储结构和遍历算法；掌握二叉树的定义、基本性质、存储结构、和各种运算。,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林的表示方法,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,6.1 树的类型定义,6.1 树的逻辑结构及其操作,.树（Tree)是一个非空的有限元素的集合，元素之间具有如下关系：由且仅有一个特殊元素，他没有前驱（称为树根Root）,其余元素都有且仅有一个前驱，所有元素可以有零个或多个后继。,A,B,C,D,E,F,G,H,I,
2、J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,例如:,树形结构,全校学生档案管理的组织方式,树形结构 结点间具有分层次的连接关系,现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树。否则:(1)在D中存在唯一的称
3、为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm，其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,基本操作：,查 找 类,插 入 类,删 除 类,Root(T)/求树的根结点,查找类：,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,RightSibling(T,cur_e)/求当前结点的右兄弟,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,Traverse
4、Tree(T,Visit()/遍历,InitTree(&T)/初始化置空树,插入类：,CreateTree(&T,definition)/按定义构造树,Assign(T,cur_e,value)/给当前结点赋值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,树中的一个数据元素,分支的个数,树中所有结点的度的最大值,度为零的结点,
5、度大于零的结点,D,H,I,J,M,内部结点:,孩子结点:,双亲结点:,兄弟结点:,除根之外的分支结点,结点的子树的根称为该结点的孩子（后继）,一个结点是它各子树的根结点的双亲（前驱）,具有相同双亲的结点,D,H,I,J,M,祖先:,子孙:,从根结点到该结点路径上所有结点都称为该结点的祖先。,该结点所有子树上的结点都称为该结点的子孙,(从根到结点的)路径：,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,根结点定义为第层，根的儿子定义为第层，以此类推，记作（）,树中叶子结点所在的最大层次,堂兄弟:,双亲在同一层上的结点,()有确定的根；()树根和子树根之间为有向关系。,有向树：,有
6、序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,注意：,根没有双亲，叶子没有孩子,堂兄弟的双亲是兄弟关系吗？,A,B,C,D,E,F,G,H,I,J,M,K,L,树的常见表示方法,1.直观表示法用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系，根在上，叶子在下（即树向下生长）,A,B,C,D,E,F,G,H,I,J,M,K,L,树的常见表示方法,2
7、.集合表示法根据树的集合定义，写出集合划分。,a,b,e,f,c,d,g,3.文氏图表示法集合表示的一种直观表示，用图表示集合。,4、目录表示法将树描述成一本书。书章节节小节,5、广义表表示法将树描述成广义表。子树对应的是子表,(a(b(e),(f),(c),(d,(g),已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，则该二叉树的高度为（）。假定根结点的高度为0。A.3 B.4 C.5 D.6,B,6.2 二叉树的类型定义,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,A,B,C,D,E
8、,F,G,H,K,根结点,左子树,右子树,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,二叉树的特点（和树比较）二叉树有两棵子树（可以为空）；而树可以有多棵。二叉树是有序树（有左右之分）；而树是无序树.二叉树结点的度最大是2；,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,问：具有3个结点的二叉树可能有几种不同形态？,应用举例以用二叉树表示表达式,a+b*(c-d)-e/f,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,Root(T);Value(T,e);Par
9、ent(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();,InitBiTree(,插 入 类,ClearBiTree(,删 除 类,二叉树的重要特性,用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 层时，只有一个根结点：2
10、i-1=20=1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1),性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。,一棵高度为5的二叉树中，最多包含有_个结点。假定根结点的高度为0。,63,性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。,证明：,设 二叉树结点总数 n=n0+n
11、1+n2又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1 由此，n0=n2+1。,在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.n B.n-1 C.n+1 D.2*n,思考题：,C,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,对二叉树的结点按照逐层从上到下、每层从左到右进行编号，于是每个结点都有一个序号。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,完全二叉树的特点：1、只有最后一层是不满的，不满层的结点最
12、先出现在左边 2、至多只有最下面的两层结点的度小于2 3、任何左子树的高度不会小于右子树的高度，且左右子树的高度最大相差1；4。叶子结点最多出现在最后2层上。,性质4：具有 n 个结点的完全二叉树的深度为 log2n+1。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k-1 即 k-1 log2 n k 因为 k 只能是整数，因此，k=log2n+1。,在一棵具有35个结点的完全二叉树中，该树的高度为（）。A.5 B.6 C.7 D.8,练习题：,B,性质 5：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号
13、为 i（1=i=n)的结点：,1,2,3,4,5,6,7,8,9,10,11,12,(1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2)若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,1.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。假定根结点的编号为0 A.2i B.2i-1 C.2i+1 D.2i+2,C,练习题：,6.3 二叉树的存储结构,二、二叉树的链式 存储表示,一、二叉树的顺序 存储表示,一、二叉树
14、的顺序存储表示,一、存储结构1、存储方式：用地址连续的空间单元存储二叉树的各个元素，但为了表示关系，元素存放时，首先确定一个序号，该序号是对二叉树按照完全二叉树形式编号而得,T16,例如:,特点：层次关系非常明确，双亲i/2,孩子2i,2i+1，但是必须知道结点的编号。必须按完全二叉树的形式存储，将造成存储的浪费。,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,缺点：插入、删除需要移动元素，空间效率低。,#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TEl
15、emType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;,二叉树的顺序存储表示虚拟实现,二、二叉树的链式存储表示,1.二叉链表,2三叉链表,3双亲链表,4线索链表,存储方式：用任意的空间单元来存储二叉树的各个元素，在存储元素的同时，也存储其左右孩子的地址。,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1.二叉链表,特点:,占用空间不随树的形态变化 n个结点的二叉树，占用空间为：n*(存储一个元素的空间+2*存储一个指针的空间）对求孩子操作容易，但求双亲难；插入、删除元素不需要移动，但调整指针多；空指针多,多
16、少?,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,结点结构:,typedef struct TriTNode/结点结构 TElemType data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;
17、/双亲指针 TriTNode,*TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,0123456,data parent,结点结构:,3双亲链表,LRTag,LRRRL,typedef struct BPTNode/结点结构 TElemType data;int*parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode typedef struct BPTree/树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTre
18、e,6.4二叉树的遍历,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,五、遍历算法的应用举例,四、中序遍历算法的非递归描述,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结点的信息等。,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树
19、）后左（子树）的遍历。,一、按层遍历算法,void Levelorder(BiTree*BT)const MaxLength=30;BiTree*qMaxLength;/定义队列 int front=0,rear=0;/定义队首和队尾指针 BiTree*p;if(BT!=NULL)/将树根指针进队 qrear=BT;rear=(rear+1)%MaxLength;,while(front!=rear)p=qfront;front=(front+1)%MaxLength;coutdataleft!=NULL)qrear=p-left;rear=(rear+1)%MaxLength;if(p-ri
20、ght!=NULL)qrear=p-right;rear=(rear+1)%MaxLength;/while end,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先（根）序的遍历算法：,bigin,end,先序遍历顺序:,A,B,D,F,G,C,E,H,先（根）序的遍历算法：,1,2,3,4,5,6,7,8,9,10,11,12,输出序列：1,2,4,8,9,5,10,11,3,6,12,7,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访
21、问根结点；（3）中序遍历右子树。,中（根）序的遍历算法：,bigin,end,中序遍历顺序:,A,B,D,F,G,C,E,H,中（根）序的遍历算法：,1,2,3,4,5,6,7,9,10,11,12,输出序列：4,9,2,10,5,11,1,12,6,3,7,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后（根）序的遍历算法：,bigin,end,后序遍历顺序:,F,G,D,B,H,E,C,A,后（根）序的遍历算法：,1,2,3,4,5,6,7,9,10,11,12,输出序列：9,4,10,11,5,2,12,6,7,3,1,已知一棵二叉树的静
22、态数组表示（即顺序存储表示）如下，其中0表示空指针，请分别写出该二叉树的前序、中序、后序遍历的序列。,前序序列：20 8 5 15 10 18 46 30 35 中序序列：5 8 10 15 18 20 30 35 46 后序序列：5 10 18 15 8 35 30 46 20,假定一棵二叉树的广义表表示为a(b(c),d(e,f)，分别写出对它进行前序、中序、后序、按层遍历的结果。前序：_ 中序：_ 后序：_ 按层：_,软件设计师 2004上半年,设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是_(10)_。Ax是
23、y的左兄弟 Bx是y的右兄弟Cx是y的祖先 Dx是y的后裔,C,三、算法的递归描述,void Preorder(BiTree T,void(*visit)(TElemType/遍历右子树,Void PreOderTraverse(BiTree T)if(T!=NULL)visit(T-data);PreOrderTraverse(T-lchild);PreOrderTraverser(T-rchild);/*先序遍历*/,返回,返回,返回,返回,A,C,B,D,返回,void InorderTraverse(BiTree T,void(*visit)(TElemType/遍历右子树,中序遍历算
24、法,void InorderTraverse(BiTree T,void(*visit)(TElemType/访问结点,后序遍历算法,四、中序遍历算法的非递归描述,BiTNode*GoFarLeft(BiTree T,Stack*S)if(!T)return NULL;while(T-lchild)Push(S,T);T=T-lchild;return T;,void Inorder_I(BiTree T,void(*visit)(TelemType/栈空表明遍历结束/while/Inorder_I,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数(先序遍历),2、求二叉树的深度(后序遍
25、历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,5、二叉树的其他运算和习题,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,void CountLeaf(BiTree T,int/if/CountLeaf,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然
26、后加 1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,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;,3、复制二叉树,其基本操作为：生成一个结点。,根元素,T,左子树,右子树,根元素,NEWT,左子树,右子树,左子树,右子树,(后序遍历),BiTNode*GetTreeNode(TE
27、lemType item,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;,生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr),BiTNode*CopyTree(BiTNode*T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树 else newlptr=NULL;if(T-rchild)n
28、ewrptr=CopyTree(T-rchild);/复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;/CopyTree,A,B,C,D,E,F,G,H,K,D,C,B,H,K,G,F,E,A,例如：下列二叉树的复制过程如下：,newT,4、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,按照给定的先序序列建立二叉链表,由二叉树的先序和中序序列建树,按照给定的先序序列建立二叉链表根 左子树 右子树 定义一棵二叉树,例如:,A,B,C,D,以空白字符“”表示,A(B(,C
29、(,),D(,),空树,只含一个根结点的二叉树,A,以字符串“A”表示,以下列字符串表示,Status CreateBiTree(BiTree/CreateBiTree,A B C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,
30、a,b,c,d,e,f,g,先序序列中序序列,已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：_,C,B,F,E,I,J,H,G,D,A,已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为0）和度为2、度为1的结点及叶结点个数。中根序列：c,b,d,e,a,g,i,h,j,f后根序列：c,e,d,b,i,j,h,g,f,a 高度：_ 度为2：_ 度为1：_ 叶子：_,高度：5 度为2：3 度为1：3 叶子：4,五、二叉树其他运算,1.初始化二叉树 void Ini
31、tBTree(BiTree,3.清除二叉树,void DeleteBTree(BiTree,1、已知二叉树中的结点类型用比BiTreeNode表示，被定义为:struct BiTreeNode datatype data;BiTreeNode*leftChild,*rightChild,*parent;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。BiTreeNode*PN(BiTreeNode*T,datatype
32、算法功能：,从树根指针为T的二叉树中查找值为x的结点，返回指向父结点的指针,5、已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode char data;BinTreeNode*leftChild,*rightChild;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a(b(a,d(f),c(e(,a(k),b)，整数变量C的值为0，若：(1)执行BTC1(bt,a,C)调用后，C的值为_;(2)执行BTC1(bt,b,C)调用后，C的值为_;(3
33、)执行BTC1(bt,c,C)调用后，C的值为_;(4)执行BTC1(bt,g,C)调用后，C的值为_;void BTC1(BinTreeNode*BT,char x,int,3、已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode ElemType data;BinTreeNode*leftChild,*rightChild;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。int DST(BinTreeNode*算法功能：,删
34、除根结点为x的子树，若删除成功则返回1，否则返回0,6.5线索二叉树,何谓线索二叉树？线索链表的遍历算法 如何建立线索链表？,一、何谓线索二叉树？,遍历二叉树的结果是，求得结点的一个线性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列: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,二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈
35、。,对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是B D C A H G K F E意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。,讨论2.如何获得这种“直接前驱”或“直接后继”？有何意义？,讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？,空指针的个数=n+1,A,B,C,D,E,F,G,H,K,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”,与其相应的二叉树，称作“线索二叉树”,包含“线索”的存储结构，称作“线索链表”,A B C D E F G H K,D,C,B,E,A,B,C,D,E,F,G,H,K,线索方法：利
36、用二叉树的空指针来记录线索 假设二叉树有N个结点，于是有N+1个空指针，所以可以记录N+1个线索。要记录所有的线索，需要2N个指针，因此，这种线索方法，只是记录了部分线索。,结点的左子树为空，则左指针记录该结点的前驱线索。,结点的右子树为空，则右指针记录该结点的后继 线索。,每个结点增加两个域：fwd和bwd；,存放前驱指针,存放后继指针,如何预存这类信息？有两种解决方法：,与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子；否则，rc
37、hild指向其直接后继(即线索)。,缺点：空间效率太低！,问题：计算机如何判断是孩子指针还是线索指针？,如何区别？,约定:,当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,问：增加了前驱和后继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。,如何区分是子树还是线索？,typedef struct BiThrNod TElemType data;struct BiThrNode*lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree
38、;,线索链表的类型描述：,typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索,悬空？NIL,悬空？NIL,解：对该二叉树中序遍历的结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例：画出以下二叉树对应的中序线索二叉树。,线索二叉树的生成线索化,线索化过程就是在遍历过程中修改空指针的过程,注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G,对应的中序线索二叉树存储结构如图所示：,二、线索链表的遍历算法:,for(p=firstNode(T);p;p=Succ(p)
39、Visit(p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,例如:对中序线索化链表的遍历算法,中序遍历的第一个结点？,在中序线索化链表中结点的后继？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,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;/第
40、一个结点 while(p-RTag=Thread/p进至其右子树根/InOrderTraverse_Thr,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,三、如何建立线索链表？,按中序建立线索链表（按中序线索化二叉树）,1、若结点没有左子树，则令其左指针指向它的“前驱”并将左指针类型标志改为“1”；,2、若结点没有右子树，则令其右指针指向它的“后继”并将右指针类型标志改为“1”；,T,void InThreading(BiThrTree p)if(p)/对以p为根的非空
41、二叉树进行线索化 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,Status InOrderThreading(BiThrTree/InOrderThreading,if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pr
42、e=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;,Status InOrderThreading(BiThrTree/InOrderThreading,void InThreading(BiThrTree p)if(p)InThreading(p lchild);/左子树线索化 if(!p lchild)p LTag=1;p lchild=pre;if(!pre rchild)pre RTag=1;pre rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThrea
43、ding(p rchild);/右子树线索化/InThreading,1,1,1,1,1,1,1,1,1,1,1,1,T,0,Status InOrderThreading(BiThrTree/InOrderThreading,1,1,1,1,1,1,T,0,A,G,E,I,D,J,H,C,F,B,例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。,A,Tag=1表示线索:Ltag=1表示前驱Rtag=1表示后继,6.6 树和森林 的表示方法,树的四种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,四：树的存储结构（孩子存储）,树的存储结构
44、之一（双亲存储）,1、存储方式：用任意空间单元来存放树的各个元素，在存放的同时还存放其双亲的位置。,data,parent,A,B,C,D,E,F,G,0 A-11 B 02 C 03 D 04 E 2 5 F 26 G 5,r=0n=7,data parent,特点：求双亲容易，求孩子难,typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;,data parent,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodes MAX_TREE_SIZE;
45、int r,n;/根结点的位置和结点个数 PTree;,树结构:,存储方式：用连续单元空间来存放树的各个元素，在存放该元素的同时还存放所有孩子的存储地址（链表）。,data:数据元素的值sonlink:指针，第一个孩子的结点。snop:孩子的存储位置next:下一个孩子的结点,二、孩子链表表示法:,A,B,C,D,E,F,G,0 A-11 B 02 C 03 D 04 E 25 F 26 G 5,r=0n=7,data firstchild,1 2 3,4 5,6,-1000224,特点：求孩子、找兄弟容易，但求双亲难,typedef struct CTNode int child;struc
46、t CTNode*next;*ChildPtr;,孩子结点结构:,child next,C语言的类型描述:,typedef struct Elem data;int parent;ChildPtr firstchild;/孩子链的头指针 CTBox;,双亲结点结构,data firstchild,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,树结构:,存储方式：用任意空间单元来存放树的各个元素，在存放该元素的同时还存放第一个孩子的存储地址。和右兄弟的存储地址。,data:数据元素的值fch:指针，指向第一个
47、儿子结点nsib:指针，指向其右兄弟结点,三、树的二叉链表(孩子-兄弟）存储表示法,A,B,C,D,E,F,G,AB C E D F G,root,AB C E D F G,特点：便以实现除父结点之外的各种操作,typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,结点结构:,firstchild data nextsibling,四：树的存储结构（孩子存储）,存储方式：用任意单元空间来存放树的各个元素，在存放该元素的同时还存放各个孩子的存储地址。,定长结点
48、,data:数据元素c1c2cdi：指针，指向孩子结点di：结点的度,不定长结点,data:数据元素c1c2cd：指针，指向孩子结点d：结点的度,a,b,c,d,e,f,g,h,i,优点：占用存储空间少缺点：结点不易实现,不定长结点,定长结点,树、森林和二叉树的转化,森林:m(m=0)棵互不相交的树的集合。F=T1,T2,Tm,一：树、森林和二叉树的转换,树与二叉树的转换,转换步骤：step1:将树中同一结点的兄弟相连;,加线,抹线,旋转,讨论1：树如何转为二叉树？,孩子兄弟表示法,step2:保留结点的最左孩子连线，删除其它孩子连线；,step3:将同一孩子的连线绕左孩子旋转45度角。,方法
49、：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,特点是？根结点没有右孩子！,二叉树 树如果结点是双亲的左儿子，则将该结点的右儿子，右儿子的右儿子，均与其双亲相连。然后去掉双亲到右儿子的连线。,由森林转换成二叉树的转换规则为:,同树与二叉树转换类似,由此，树的各种操作均可对应二叉树的操作来完成。,应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。,6.7树和森林的遍历,一、树的遍历,二、森林的遍历,三、树的遍历的应用,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。
50、,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,A B C DE F G H I J K,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,B C DE F G H I J K,1森林中第一棵树的根结点；,2森林中第一棵树的子树森林；,3森林中其它树构成的森林。,森林由三部分构成：,1.先序遍历,森林的遍历,若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子
