第6章　树和二叉树n.ppt

《第6章　树和二叉树n.ppt》由会员分享，可在线阅读，更多相关《第6章　树和二叉树n.ppt（198页珍藏版）》请在三一文库上搜索。

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

2、,I,J,M,K,L,A( B(E, F(K, L), C(G), D(H, I, J(M) ),T1,T3,T2,树根,例如:,树形结构,全校学生档案管理的组织方式,树形结构 结点间具有分层次的连接关系,现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关系等。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，

3、则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素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) / 求当前结点的右兄弟,Tr

4、eeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( 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) / 删除结点

5、p的第i棵子树,基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,树中的一个数据元素,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,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,树的常见表示方

7、法,1.直观表示法 用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系，根在上，叶子在下（即树向下生长）,A,B,C,D,E,F,G,H,I,J,M,K,L,树的常见表示方法,2.集合表示法 根据树的集合定义，写出集合划分。,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 ) )，则该二叉树的高度为（

8、 ）。假定根结点的高度为0 。 A. 3 B. 4 C. 5 D. 6,B,6.2 二叉树的类型定义,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,二叉树的特点（和树比较） 二叉树有两棵子树（可以为空）；而树可以有多棵。 二叉树是有序树（有左右之分）；而树是无序树. 二叉树结点的度最大是2；,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R

9、,R,右子树为空树,L,左子树为空树,左右子树均不为空树,问：具有3个结点的二叉树可能有几种不同形态？,应用举例 以用二叉树表示表达式,a+b*(c-d)-e/f,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,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

10、, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,InitBiTree(,插 入 类,ClearBiTree(,删 除 类,二叉树 的重要特性,用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),性质 2 ： 深度为 k 的二叉树上至多

11、含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,一棵高度为5的二叉树中，最多包含有_个结点。假定根结点的高度为0。,63,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。 A

12、. 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、只有最后一层是不满的，不满层的结点最先出现在左边 2、至多只有最下面的两层结点的度小于2 3、任何左子树的高度不会小于右子树的高度，且左右子树的高度最大相差1； 4。叶子结点最多出现在最后2层上。,

13、性质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 的编号，则对完全二叉树中任意一个编号为 i （1=i=n)的结点：,1,2,3,4,5,6,7,8,9,10,11,12,(1) 若 i=1，则该结点是二叉树的

14、根，无双亲，否则，编号为 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 二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,一、 二叉树的顺序存储表示,一、存储结构 1、存储方式：用地址连续的空间单元存储二叉树的各个元素，但为了

15、表示关系，元素存放时，首先确定一个序号，该序号是对二叉树按照完全二叉树形式编号而得,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 TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结

16、点 SqBiTree bt;,二叉树的顺序存储表示虚拟实现,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4线索链表,存储方式：用任意的空间单元来存储二叉树的各个元素，在存储元素的同时，也存储其左右孩子的地址。,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1. 二叉链表,特点:,占用空间不随树的形态变化 n个结点的二叉树，占用空间为： n*(存储一个元素的空间+2*存储一个指针的空间） 对求孩子操作容易，但求双亲难； 插入、删除元素不需要移动，但调整指针多； 空指针多,多少?,typedef struct BiTNode / 结点结构

17、 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; /双亲指针 TriTNode,

18、 *TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,0 1 2 3 4 5 6,data parent,结点结构:,3双亲链表,LRTag,L R R R L,typedef struct BPTNode / 结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根

19、结点的位置 BPTree,6.4 二叉树的遍历,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,五、遍历算法的应用举例,四、中序遍历算法的非递归描述,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结 点的信息等。,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2

20、先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。,一、按层遍历算法,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) q

21、rear=p-left; rear=(rear+1)% MaxLength; if(p-right!=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

22、,8,9,5,10,11,3,6,12,7,若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （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

23、,4,5,6,7,9,10,11,12,输出序列：9,4,10,11,5,2,12,6,7,3,1,已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其中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和

24、y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是_(10)_。 Ax是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); /*先序遍历*/,返回,返回,

25、返回,返回,A,C,B,D,返回,void InorderTraverse (BiTree T, void( *visit)(TElemType / 遍历右子树 ,中序遍历算法,void PostOrderTraverse (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 In

26、order_I(BiTree T, void (*visit) (TelemType / 栈空表明遍历结束 / while / Inorder_I,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍历),2、求二叉树的深度(后序遍历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,5、二叉树的其他运算和习题,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,void CountLeaf (BiTree T

27、, int / if / CountLeaf,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1

28、+ (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,3、复制二叉树,其基本操作为：生成一个结点。,根元素,T,左子树,右子树,根元素,NEWT,左子树,右子树,左子树,右子树,(后序遍历),BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchi

29、ld = 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 ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, new

30、rptr); 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( , ),D( , ),空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,Status CreateBiTree

31、(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,a,b,c,d,e,f,g,先序序列中序序列,已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。 前序序列：A, B,

32、 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 InitBTree(BiT

33、ree ,3. 清除二叉树,void DeleteBTree(BiTree ,1、 已知二叉树中的结点类型用比BiTreeNode表示，被定义为: struct BiTreeNode datatype data; BiTreeNode *leftChild, *rightChild, *parent; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。 BiTreeNode* PN (BiTreeNode * T, d

34、atatype 算法功能：,2已知二叉搜索树中的结点类型用BinTreeNode表示，被定义:struct BinTreeNode ElemType data; BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定pt所指向的二叉搜索树的广义表表示为: 25 (10 (5, 16 (12) ), 40 (32 ( , 38) ) )，按照下面算法， (1) 执行unknown ( pt, 40 ) 调用后返回的值为_。 (2) 执行unknown ( pt, 38 )

35、 调用后返回的值为_。 (3) 执行unknown ( pt, 5 ) 调用后返回的值为_。 (4) 执行unknown ( pt, 60 ) 调用后返回的值为_。 int unknown ( BinTreeNode* t, ElemType x ) if ( t = NULL ) return 0; else if ( t-data = x ) return 1; else if ( t-data x ) return 1+unknown ( t-leftChild, x ); else return 1+unknown ( t-rightChild, x ); ,3、 已知二叉树中的结点类

36、型用比BiTreeNode表示，被定义为: struct BiTreeNode datatype data; BiTreeNode *leftChild, *rightChild, *parent; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。 BiTreeNode* PN (BiTreeNode * T, datatype 算法功能：,从树根指针为T的二叉树中查找值为x的结点，返回指向父结点的指针,4、 已知二

37、叉树中的结点类型用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) 执行BT

38、C1( bt, c, C) 调用后，C的值为_; (4) 执行BTC1( bt, g, C) 调用后，C的值为_; void BTC1( BinTreeNode* BT, char x, int ,5、 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data; BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。 int DST

39、 ( BinTreeNode* 算法功能：,删除根结点为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,空指针的个数=n+1,A,B,C,D,E,F,G,H,K,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树，称作 “线索二叉树”,包含

40、“线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,A,B,C,D,E,F,G,H,K, 每个结点增加两个域：fwd和bwd；,存放前驱指针,存放后继指针,如何预存这类信息？有两种解决方法：, 与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子； 否则，rchild指向其直接后继(即线索) 。,缺点：空间效率太低！,问题：计算机如何判断是孩子指针还是线索指针？,如何区别？,约定:,

41、当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,问：增加了前驱和后继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。,如何区分是子树还是线索？,线索方法：利用二叉树的空指针来记录线索 假设二叉树有N个结点，于是有N+1个空指针，所以可以记录N+1个线索。要记录所有的线索，需要2N个指针，因此，这种线索方法，只是记录了部分线索。,结点的左子树为空，则左指针记录该结点的前驱线索。,结点的右子树为空，则右指针记录该结点的后继 线索。,typedef struct BiThrNod TElemType data; st

42、ruct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,线索链表的类型描述：,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,悬空？ NIL,悬空？ NIL,解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例：画出以下二叉树对应的中序线索二叉树。,线索二叉树的生成线索化,线索化过程就是在遍

43、历过程中修改空指针的过程,注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G,对应的中序线索二叉树存储结构如图所示：,二、线索链表的遍历算法:,for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,例如: 对中序线索化链表的遍历算法, 中序遍历的第一个结点 ？, 在中序线索化链表中结点的后继 ？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,void

44、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) returen ERROR; while (p-RTag=Thread / p进至其右子树根 / InOrderTraverse_Thr,在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。遍历过 程中，附设指针pre

45、, 并始终保持指 针pre指向当前访问的、指针p所指 结点的前驱。,三、如何建立线索链表？,按中序建立线索链表（按中序线索化二叉树）,1、若结点没有左子树，则令其左指针指向它的“前驱”并将左指针类型标志改为 “1”；,2、若结点没有右子树，则令其右指针指向它的“后继”并将右指针类型标志改为 “1”；,T,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,Status InOrderThreading(BiThrTree / InOrderT