《数据结构课件树》由会员分享，可在线阅读，更多相关《数据结构课件树（58页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构North China Electric Power UniversityData Structure华北电力大学计算机科学与工程系华北电力大学计算机科学与工程系Dept. of Computer Science&Engineering of North China Electric Power University第五章第五章 树树 基本术语基本术语 树的基本操作和存储结构树的基本操作和存储结构 二叉树二叉树North China Electric Power University 二叉树的遍历及线索二叉树二叉树的遍历及线索二叉树 树的遍历树的遍历 哈夫曼树及其应用哈夫曼树及
2、其应用基本术语基本术语North China Electric Power University 树型结构是一类重要的非线性数据结构，其中以二叉树树型结构是一类重要的非线性数据结构，其中以二叉树最为常用。树是以分支关系定义的层次结构，它为计算机应最为常用。树是以分支关系定义的层次结构，它为计算机应用中出现的具有层次关系或分支关系的数据提供了一种自然用中出现的具有层次关系或分支关系的数据提供了一种自然的表示方法。用树结构描述的信息模型在客观世界普遍存在。的表示方法。用树结构描述的信息模型在客观世界普遍存在。计算机科学与工程系计算机科学与工程系办公室办公室教研室教研室实验室实验室研究室研究室行行政
3、政办办公公室室总总支支办办公公室室计计算算机机教教研研室室软软件件教教研研室室软软件件实实验验室室综综合合实实验验室室数数字字逻逻辑辑实实验验室室组组成成原原理理试试验验室室管管理理信信息息系系统统研研究究室室知知识识工工程程研研究究室室微微机机应应用用研研究究室室North China Electric Power University 树的定义：树的定义：树是树是n(n0)个结点的有限集个结点的有限集T,在一棵非空在一棵非空树中：树中： 1)有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点； 2)当当n1时时,其余结点可分为其余结点可分为m(m0)个互不相交的个互不相交的有限
4、集合有限集合T1,T2,Tm,其中每个集合本身又是一棵树，其中每个集合本身又是一棵树，并且称为根的子树。并且称为根的子树。树的定义可以用如下形式化描述来表示：树的定义可以用如下形式化描述来表示：Tree=(D,R)其中其中:D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合;若若D只含有只含有一个元素一个元素,则则R为空集为空集,否则否则R是是D上的某个二元关系上的某个二元关系H的集合的集合,即即R=H,H为如下描述的二元关系为如下描述的二元关系:树的几种表示方法树的几种表示方法：1)有且仅有一个结点没有前驱，该结点被称为树的根；有且仅有一个结点没有前驱，该结点被称为树的根；2)除
5、树根结点外，其余每个结点有且仅有一个前驱结点；除树根结点外，其余每个结点有且仅有一个前驱结点；3)包含树根结点在内的每个结点，可以有任意多个包含树根结点在内的每个结点，可以有任意多个(包含包含 0个个)后继。后继。ABC DEFGHIJK LM1)二元组表示二元组表示D=A,B,C,D,E,F,G,H,I,J,K,L,MR=,North China Electric Power University4) 广义表表示法：广义表表示法：A(B(E,F(K,L),C(G),D(H,I,J(M)ABEKLFCGHIMDJ2)集合图表示集合图表示3)凹入表表示凹入表表示North China Elect
6、ric Power University树型结构和线性结构的比较树型结构和线性结构的比较树型结构树型结构线性结构线性结构根结点无前驱结点根结点无前驱结点第一个数据元素无前驱第一个数据元素无前驱多个叶子结点无后继多个叶子结点无后继最后一个数据元素无后继最后一个数据元素无后继其它数据元素有一个其它数据元素有一个前驱和多个后继前驱和多个后继其它元素有且仅有一个直接其它元素有且仅有一个直接前驱和一个直接后继前驱和一个直接后继North China Electric Power University树中的基本术语树中的基本术语：ABC DEFGHIJK LM1.结点、结点的度、树的度结点、结点的度、树的
7、度2.叶子结点、分支结点叶子结点、分支结点3.孩子、双亲、兄弟、孩子、双亲、兄弟、 堂兄弟、祖先、子孙堂兄弟、祖先、子孙4.结点的层次、树的深度结点的层次、树的深度5.有序树和无序树有序树和无序树6.森林森林BC DEFGHIJK LMNorth China Electric Power University树的性质树的性质：性质性质1:树中的结点数等于所有结点的度加树中的结点数等于所有结点的度加1。ABC DEFGHIJK LM证明：除树的根结点外每个证明：除树的根结点外每个 结点有且只有一个直结点有且只有一个直 接前驱，除树的根结接前驱，除树的根结 点之外的结点数等于点之外的结点数等于 所
8、有结点的分支数。所有结点的分支数。性质性质2:度为度为k的树中第的树中第i层至多有层至多有ki-1个结点。个结点。性质性质3:深度为深度为h的的k叉树至多有叉树至多有(kh-1)/(k-1)个结点。个结点。性质性质4:具有具有n个结点的个结点的k叉树的最小深度为叉树的最小深度为 logk(n(k-1)+1) 。North China Electric Power University树的基本操作和存储结构树的基本操作和存储结构树的基本运算树的基本运算1.Root(T):求树求树T的根结点，若的根结点，若T为空则返回结果为为空则返回结果为“空空”。2.Parent(T,x):求结点求结点x在树在
9、树T上的双亲结点，若结点上的双亲结点，若结点x是树是树T的根的根 结点或结点或x不在树不在树T中，则返回结果为中，则返回结果为“空空”。3.Initiate(T):置置T为空树。为空树。4.Child(T,x,i):求树求树T上结点上结点x的第的第i个孩子，若个孩子，若x不在树不在树T上或上或x 没有第没有第i个孩子，则返回结果为个孩子，则返回结果为“空空”。5.Create(x,T1,T2,Tk):建立一棵以建立一棵以x为根，以为根，以T1,T2,Tk为第为第1,2, 3,k棵子树的树。棵子树的树。6.Delete(T,x,i):删除树删除树T上结点上结点x的第的第i棵子树，若结点棵子树，若
10、结点x无第无第i棵子棵子 树，则为空操作。树，则为空操作。7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结按某个次序依次访问树中的各个结点，并使每个结 点只被访问一次。点只被访问一次。North China Electric Power University树的存储结构树的存储结构1.孩子表示法孩子表示法 由于树中每个结点可能有多棵子树，可用多重链表，即由于树中每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结每个结点有多个指针域，其中每个指针指向一棵子树的根结点，则结点形式有如下两种：点，则结点形式有如下两种：datachil
11、d1child2childddatachild1child2childddegree 在第一种形式中，结点是同构的，存储空间浪费较大，在第一种形式中，结点是同构的，存储空间浪费较大，在第二种形式中，结点是不同构的，虽能节约存储空间，但在第二种形式中，结点是不同构的，虽能节约存储空间，但实现和运算很不方便。实现和运算很不方便。(1)(2)North China Electric Power University 可以把每个结点的孩子结点排列起来，看成一个线性表，可以把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，且以单链表作存储结构，n个结点有个结点有n个孩子链表，个孩子链表
12、，n个头指针个头指针又组成一个线性表，为了便于查找，可用向量表示。又组成一个线性表，为了便于查找，可用向量表示。Type link=node; node=record child:ElemType; next:link; end; tree=Array1.maxn of link; 1234562345612345623456123456011222North China Electric Power University2.孩子兄弟表示法孩子兄弟表示法 又称二叉链表表示法，即以二叉链表作树的存储结构，链又称二叉链表表示法，即以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个
13、孩子结点和下一表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为个兄弟结点，分别命名为first-child和和nextsibling。data first-child nextsibling123456123456 在孩子兄弟表示法中，要找结点在孩子兄弟表示法中，要找结点x的第的第i个孩子个孩子,则只要先从则只要先从first-child域找到第一个孩子结点上，然后沿着该孩子结点的域找到第一个孩子结点上，然后沿着该孩子结点的nextsibling域连续走域连续走i-1步，便可找到步，便可找到x的第的第i个孩子。个孩子。North China Electric Pow
14、er University3.双亲表示法双亲表示法 用一个数组顺序地存放树的各个结点，结点存放的顺序是任用一个数组顺序地存放树的各个结点，结点存放的顺序是任意的。每一结点有两个域组成：数据域和指针域，分别存储树上意的。每一结点有两个域组成：数据域和指针域，分别存储树上结点中的数据元素和用于指示本结点之双亲所在的存储结点。结点中的数据元素和用于指示本结点之双亲所在的存储结点。 指针域的类型定义有两种：高级语言中的指针类型和整型指针域的类型定义有两种：高级语言中的指针类型和整型或子界类型，与之对应的链表分别称为动态链表和静态链表。或子界类型，与之对应的链表分别称为动态链表和静态链表。静态双亲链表的
15、定义：静态双亲链表的定义：const size=结点数结点数;Type node=record data:ElemType; parent:0.size; end;stalist=array1.size of node;123456123456132456dataparent011333结点序号结点序号North China Electric Power University二叉树二叉树 二叉树是一种重要的数据结构类型，它有许多良二叉树是一种重要的数据结构类型，它有许多良好的性质和简单的物理表示，它的特点是最多有两个好的性质和简单的物理表示，它的特点是最多有两个孩子，并且二叉树的子树有左右之分
16、，且其子树的顺孩子，并且二叉树的子树有左右之分，且其子树的顺序不能任意颠倒。序不能任意颠倒。二叉树的定义二叉树的定义 二叉树是有二叉树是有n(n0)0)个结点的有限集合，此集合或个结点的有限集合，此集合或者是空的，或者是由一个根结点加上两棵分别称为左者是空的，或者是由一个根结点加上两棵分别称为左右子树的、互不相交的二叉树组成。右子树的、互不相交的二叉树组成。注意：注意：二叉树和树是两个不同的概念，树的子树不必区分其次二叉树和树是两个不同的概念，树的子树不必区分其次序，而二叉树的子树有左右之分，另外，二叉树也不能简单地序，而二叉树的子树有左右之分，另外，二叉树也不能简单地看成是一有序树，因为只有
17、一棵子树时，无法区分其次序。看成是一有序树，因为只有一棵子树时，无法区分其次序。North China Electric Power University二叉树的基本形态：二叉树的基本形态：(空空)根根根根左左子子树树根根右右子子树树根根左左子子树树右右子子树树具有三个结点的二叉树具有以下五种基本形态：具有三个结点的二叉树具有以下五种基本形态：North China Electric Power University两种特殊形态的二叉树两种特殊形态的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点, ,或者为叶结点，或者为叶结点， 或者具有两或者具有两棵非空子树棵非空子树, ,并且叶结点都集并
18、且叶结点都集中在二叉树的最下面一层中在二叉树的最下面一层. .这这样的二叉树为满二叉树样的二叉树为满二叉树. .1. . 满二叉树满二叉树 若一棵二叉树中只有最下若一棵二叉树中只有最下面两层的结点的度可以小于面两层的结点的度可以小于2, ,并且最下面一层的结点并且最下面一层的结点( (叶结叶结点点) )都依次排列在该层从左至都依次排列在该层从左至右的位置上。这样的二叉树为右的位置上。这样的二叉树为完全二叉树完全二叉树. .2. .完全二叉树完全二叉树North China Electric Power University1. . 一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1
19、个结点个结点( (i 1) )。证明证明( (采用归纳法采用归纳法) ) ( (1).).当当i=1=1时时, ,结论显然正确。非空二叉树的第结论显然正确。非空二叉树的第1层有且层有且 仅有一个结点仅有一个结点, ,即树的根结点即树的根结点. .( (2).).假设对于第假设对于第j层层( (1 j i1) )结论也正确结论也正确, ,即第即第j层最层最多多 有有2j-1个个结点结点. .( (3).).由定义可知由定义可知, , 二叉树中每个结点最多只能有两个二叉树中每个结点最多只能有两个 孩子结点。若第孩子结点。若第i1层的每个结点都有两棵非空子层的每个结点都有两棵非空子 树树, ,则第则
20、第i层的结点数目达到最大层的结点数目达到最大. . 而第而第i1层最多层最多 有有2i2个结点已由假设证明个结点已由假设证明, ,于是于是, ,应有应有 2 2i2 = 2i1证毕证毕. .二叉树的性质二叉树的性质North China Electric Power University2. . 深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h -1-1个结点个结点. .证明证明: : 由性质由性质1 1可知可知, ,若深度为若深度为h h的二叉树的每一层的结点数的二叉树的每一层的结点数目都达到各自所在层的最大值目都达到各自所在层的最大值, ,则二叉树的结点总数一定则二叉树的结点总数一
21、定达到最大。即有达到最大。即有 20+21+22+2i-1+ +2h-1 = 2h-1证毕证毕. .华电计算机系华电计算机系North China Electric Power University3. . 若非空二叉树有若非空二叉树有n0个叶结点个叶结点, ,有有n2个度为个度为2的结点的结点, , 则则 n0=n2+1 证明证明: : 设该二叉树有设该二叉树有n1个度为个度为1的结点的结点, ,结点总数为结点总数为n, ,有有 n=n0+n1+n2 -(1) 设二叉树的分支数目为设二叉树的分支数目为B, ,有有 B=n-1 -(2)这些分支来自于度为这些分支来自于度为1的结点与度度为的结点
22、与度度为2结点结点, ,即即 B=n1+2n2 -(3)联列关系联列关系( (1),(),(2) )与与( (3),),可得到可得到 n0=n2+1证毕证毕. .4. . 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度h= log2n +1. .证明证明: : ( (略略) ) 推论：推论： n0=n2+2n3+3n4+ +(m-1)nm +1North China Electric Power University5. 若对具有若对具有n个结点的完全二叉树按照层次从上到下个结点的完全二叉树按照层次从上到下,每层每层从从 左到右的顺序进行编号左到右的顺序进行编号, 则编号为则编号为
23、i 的结点具有以下性质的结点具有以下性质: (1) 当当i=1, 则编号为则编号为i的结点为二叉树的根结点的结点为二叉树的根结点; 若若i1, 则编号为则编号为i 的结点的双亲结点的编号为的结点的双亲结点的编号为 i/2 ; (2) 若若i(2h-1)/2 ) then total:=total+1; for i:=1 to 2h-1 do 算法算法北航北航计算机系计算机系树与二叉树之间的转换树与二叉树之间的转换North China Electric Power University1. 在兄弟结点之间加一条连线；在兄弟结点之间加一条连线；2. 对每个结点，除去其最左的孩子之外，去掉该结点与
24、其他对每个结点，除去其最左的孩子之外，去掉该结点与其他 孩子之间的连线；孩子之间的连线；3. 以树的根结点为轴心，将整棵树顺时针旋转以树的根结点为轴心，将整棵树顺时针旋转45度。度。ABCDEFG HIJABCDEF GHIJABCDEF GHIJ森林与二叉树之间的转换森林与二叉树之间的转换North China Electric Power University1. 将森林中各棵树的根结点之间加一条连线；将森林中各棵树的根结点之间加一条连线；2. 对每棵树，用树的二叉树表示法相连，然后顺时针旋转对每棵树，用树的二叉树表示法相连，然后顺时针旋转45度。度。ABCDEGFHJIABEGCDFHI
25、JNorth China Electric Power University二叉树的遍历及线索二叉树二叉树的遍历及线索二叉树常用的二叉树的遍历方法常用的二叉树的遍历方法: : 1. .先序遍历先序遍历 2. .中序遍历中序遍历 3. .后序遍历后序遍历 4. .按层次遍历按层次遍历右右子子树树左左子子树树根根华电华电计算机系计算机系 按照一定的顺序按照一定的顺序( ( 原则原则 ) )对二叉对二叉树中每一个结点都访问一次树中每一个结点都访问一次( (仅访问仅访问一次一次), ), 得到一个由该二叉树的所有得到一个由该二叉树的所有结点组成的序列结点组成的序列, , 这一过程称为二这一过程称为二叉
26、树的遍历叉树的遍历. .North China Electric Power University前序序列前序序列: :A B D E J C F I原则原则: : 若被遍历的二叉树非空若被遍历的二叉树非空, , 则则 1. . 访问根结点访问根结点; ; 2. . 以前序遍历原则遍历根结点的左子树以前序遍历原则遍历根结点的左子树; ; 3. . 以前序遍历原则遍历根结点的右子树以前序遍历原则遍历根结点的右子树. .G华电计算机系华电计算机系1. . 先序遍历先序遍历ABCDEFGJINorth China Electric Power University华电计算机系华电计算机系2. . 中
27、序遍历中序遍历ABCDEFGJI中序序列中序序列: :D B J E A F I C原则原则: : 若被遍历的二叉树非空若被遍历的二叉树非空, , 则则 1. . 以中序遍历原则以中序遍历原则遍历根结点的左子树遍历根结点的左子树; ; 2. . 访问根结点访问根结点; ; 3. . 以中序遍历原则以中序遍历原则遍历根结点的右子树遍历根结点的右子树. .GNorth China Electric Power University华电计算机系华电计算机系3. . 后序遍历后序遍历ABCDEFGJI后序序列后序序列: :D J E B I F G C原则原则: : 若被遍历的二叉树非空若被遍历的二叉
28、树非空, , 则则 1. . 以后序遍历原则以后序遍历原则遍历根结点的左子树遍历根结点的左子树; ; 2. . 以后序遍历原则以后序遍历原则遍历根结点的右子树遍历根结点的右子树. . 3. . 访问根结点访问根结点; ;ANorth China Electric Power Universityprocedure Preorder( T );begin if (T nil) then writeln( T .data ); Preorder( T .lchild ); Preorder( T .rchild );end;先序遍历先序遍历 procedure Inorder( T ); begi
29、n if (T nil) then Inorder( T .lchild ); writeln( T .data ); Inorder( T .rchild ); end;中序遍历中序遍历华电华电计算机系计算机系North China Electric Power University 按层次遍历按层次遍历按层次遍历序列按层次遍历序列: A, B, C, D, E, F, G, J, Iprocedure Postorder( T );begin if (T nil) then Postorder( T .lchild ); Postorder( T .rchild ); writeln( T
30、 .data );end;后序遍历后序遍历华电计算机系华电计算机系ABCDEFGJI 例例下图是代表表达式下图是代表表达式a+b*(c-d)-e/f的二叉树的二叉树-+/a*efb-cd华电华电计算机系计算机系 a+b*c-d-e/f中序遍历序列中序遍历序列: : abcd-*+ef/-后序遍历序列后序遍历序列: : -+a*b-cd/ef先序遍历序列先序遍历序列: :North China Electric Power UniversityNorth China Electric Power University三种遍历方法的非递归算法三种遍历方法的非递归算法 用自然语言表达的算法用自然语言
31、表达的算法(1) 若若p 指向的结点非空，则将指向的结点非空，则将p指的结点的指的结点的地址地址进进 栈栈, ,然后然后, ,将将p 指向左子树的根指向左子树的根; ;(2) 若若p 指向的结点为空指向的结点为空, ,则从堆栈中退出栈顶元素则从堆栈中退出栈顶元素 送送p，访问该结点，然后访问该结点，然后, ,将将p 指向右子树的根；指向右子树的根；重复上述过程重复上述过程, ,直到直到p 为空为空, ,并且堆栈也为空。并且堆栈也为空。STACK1: M - 保存遍历过程中链结保存遍历过程中链结点点的地址的地址top - 栈顶指针栈顶指针, ,初始为初始为0p - 为遍历过程中使用的指针变量，初
32、始时指向为遍历过程中使用的指针变量，初始时指向 根结点。根结点。( (以中序遍历为例以中序遍历为例) )prchild(p)plchild(p)North China Electric Power University中序遍历中序遍历Procedure Inorder(T);Begin if t=nil then return else i:=0;p:=t; repeat while pnil do i:=i+1;si:=p;p:=p .lchild; if i0 then p:=si;i:=i-1; write(p .data); p:=p .rchild; until (i=0) and
33、(p=nil);end;North China Electric Power University先序遍历先序遍历Procedure Preorder(T);Begin if t=nil then return else i:=0;p:=t; repeat while pnil do write(p .data); if p .rchild nil then i:=i+1;si:=p .rchild; p:=p .lchild; if i0 then p:=si;i:=i-1; until (i=0) and (p=nil);end; North China Electric Power Un
34、iversity后序遍历后序遍历Procedure Postorder(T);Begin if t=nil then return else i:=0;p:=t; repeat while pnil do i:=i+1;si:=p;p:=p .lchild; while(i0) and (p=nil) do p:=si;i:=i-1; if p0 then i:=i+1;si:= -p;p:=p .rchild else p:= -p;write(p .data);p:=nil; until (i=0) and (p=nil);end; North China Electric Power U
35、niversity前序序列前序序列: : A, B, D, E, J, C, F, I, G中序序列中序序列: : D, B, J, E, A, F, I, C, G后序序列后序序列: : D, J, E, B, I, F, G, C, A前序序列前序序列: : A, B, D, E, J, C, F, I, G中序序列中序序列: : D, B, J, E, A, F, I, C, G后序序列后序序列: : ?！华电华电计算机系计算机系ABCDEFGIJ由遍历序列恢复二叉树由遍历序列恢复二叉树North China Electric Power University前序序列前序序列: : A,
36、 B, D, E, J, C, F, I, G中序序列中序序列: : D, B, J, E, A, F, I, C, GAD,B,J, EF,I,C,G前序序列前序序列: : A, B, D, E, J, C, F, I, G中序序列中序序列: : D, B, J, E, A, F, I, C, GAF,I,C,GBJ, ED前序序列前序序列: : A, B, D, E, J, C, F, I, G中序序列中序序列: : D, B, J, E, A, F, I, C, GAF,I,C,GBDEJ华电计算机系华电计算机系North China Electric Power University后
37、序序列后序序列: : D, J, E, B, I, F, G, C, A 规律规律( (前前, ,中中):): 在前序序列中找根在前序序列中找根; ; 到中序序列中分左右。到中序序列中分左右。 规律规律( (中中, ,后后):): 在后序序列中找根在后序序列中找根; ; 到中序序列中分左右到中序序列中分左右。华电华电计算机系计算机系ABCDEFGIJNorth China Electric Power University1.1.建立二叉树建立二叉树Procedure CreateBtr(var t);Begin read(ch); if ch=# then t:=nil else new(p
38、); p .data:=ch; t:=p; CreateBtr(T .lchild); CreateBtr(T .rchild); End; 二叉树遍历算法的应用示例二叉树遍历算法的应用示例North China Electric Power University2.2.统计二叉树结点个数统计二叉树结点个数BitNode(t)=0 若若t=nil1 若若t .lchild=nil and t .rchild=nilBitNode(t .lchild)+BitNode(t .rchild) 其他其他统计方法统计方法Function BitNode(t):integer;Begin if(t=ni
39、l) return(0) else if(t .lchild=nil) and (t .rchild=nil) then return (1) else nodes1:=BitNode( t .lchild); nodes2:=BitNode( t .rchild); return(nodes1+nodes2); End; North China Electric Power University3.3.交换二叉树中各结点的左右子树交换二叉树中各结点的左右子树Procedure Swap(t);Begin if(tnil) then if (t . lchildnil) or(t .rchil
40、dnil) thenp:=t .rchild; t .rchild:=t .lchild; t .lchild:=p; if (t . lchildnil) then Swap(t . lchild); if (t . rchildnil) then Swap(t . rchild);End; ABCDEF注意：这里不能用中序遍历。注意：这里不能用中序遍历。ABCEDFACFBEDNorth China Electric Power University4.4.表达式的计算表达式的计算 采用的结点结构如右图所示：采用的结点结构如右图所示：lchildrchilddatavalue 其中其中va
41、l域存放以该结点为根的子树的值：域存放以该结点为根的子树的值：-+/-*aeabcd 表达式表达式: (a-b)+(c*d)-(a/e)Procedure Postorder_val(t);Begin if(tnil) then Postorder_val(t .lchild); Postorder_val(t .rchild); case t .data +:t .val:=t .lchild .val+ t .rchild .val; else: t .val:=t .data; end case End;North China Electric Power University 利用二叉
42、链表中空的指针域指出结点在遍历序利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继列中的直接前驱和直接后继; ;这些指向前驱和后继的这些指向前驱和后继的指针称为指针称为线索线索, , 加了线索的二叉树称为加了线索的二叉树称为线索二叉树线索二叉树. . 利用链结点为空的左指针域存放该结点的直接前驱利用链结点为空的左指针域存放该结点的直接前驱的地址的地址, ,空的右指针域存放该结点直接后继的地址空的右指针域存放该结点直接后继的地址; ; 而而非空的指针域仍然存放结点的左孩子或右孩子的地址非空的指针域仍然存放结点的左孩子或右孩子的地址. . 二叉线索树的构造二叉线索树的构造 二叉线索树
43、二叉线索树North China Electric Power UniversityNIL( (a)a)先序先序NIL( (b)b)中序中序NILNIL( (c)c)后序后序线索树示例线索树示例ABDCEFGHABDCEFGHABDCEFGHNorth China Electric Power Universityltaglchilddatarchildrtag 1 表示表示 lchild(p) 为指向直接前驱的线索为指向直接前驱的线索ltag(p) = = 0 表示表示 lchild(p) 为指向左孩子的指针为指向左孩子的指针 1 表示表示 rchild(p) 为指向直接后继的线索为指向直接
44、后继的线索rtag(p) = = 0 表示表示 rchild(p) 为指向右孩子的指针为指向右孩子的指针指针与线索的区分方法之一指针与线索的区分方法之一 : :华电华电计算机系计算机系North China Electric Power University指针与线索的区分方法之二指针与线索的区分方法之二: : 不改变链结点的构造不改变链结点的构造, ,而是在作为线索的而是在作为线索的地址前加一个负号地址前加一个负号, ,即负地址表示线索即负地址表示线索, ,正地址正地址表示指针表示指针. .华电华电计算机系计算机系North China Electric Power University N
45、IL a b c d e f NIL中序线索树示例中序线索树示例-+/*-由于左由于左图图中中lchildlchild(a)(a)与与rchildrchild(f)(f)是悬空是悬空的，为了不使线索断开，这里对于所有的的，为了不使线索断开，这里对于所有的线索树将假定一个头结点，其线索树将假定一个头结点，其datadata域为空域为空或与其它结点的或与其它结点的datadata域值不同域值不同. .-+/a*efb-cd110000001100111100111111North China Electric Power University (1). 当当rtag(x)=1时时, rchild(
46、x)指出的结点就是指出的结点就是x 的直接的直接 后继结点。后继结点。 (2). 当当rtag(x)=0时时, 沿着沿着x 的右子树的根的左子树方向的右子树的根的左子树方向 往下找往下找, 直到某结点的直到某结点的 lchild 域域为线索时为线索时, 此结此结点点 就是就是x 结点直接后继结点。结点直接后继结点。 中序二叉线索树中序二叉线索树 二叉线索树的利用二叉线索树的利用 (3). 当当ltag(x)=1时时, lchild(x)指出的结点就是指出的结点就是x 的直接的直接 前驱结点。前驱结点。 (4). 当当ltag(x)=0时时, 从从x的左链沿右找下去，直到某结的左链沿右找下去，直
47、到某结 点的点的rlchild 域域为线索时为线索时, 此结点就是此结点就是x 结点直接结点直接 前驱结点。前驱结点。 North China Electric Power University后序二叉线索树后序二叉线索树 (1). 当当rtag(x)=1时时, rchild(x)指出的结点就是指出的结点就是x 的直接后继的直接后继 结点。结点。 (2). 当当rtag(x)=0时时, 从从x的双亲结点的右孩子沿着左链一直的双亲结点的右孩子沿着左链一直 往下找往下找, 直到某结点的直到某结点的 lchild 域域为线索时为线索时, 然后再看然后再看此此 结点有无右孩子，若有，则再沿着右孩子走下
48、去，如结点有无右孩子，若有，则再沿着右孩子走下去，如 此递归进行，直到一个无左、右孩子的结点便是此递归进行，直到一个无左、右孩子的结点便是x的后的后 继，若结点继，若结点x的双亲没有右孩子或右孩子就是结点本身，的双亲没有右孩子或右孩子就是结点本身， 则此双亲结点便是则此双亲结点便是x的直接后继结点。的直接后继结点。 (3). 当当ltag(x)=1时时, lchild(x)指出的结点就是指出的结点就是x 的直接前驱的直接前驱 结点。结点。 (4). 当当ltag(x)=0时时, 若若x有右孩子，则有右孩子，则x的右即为其前驱，若的右即为其前驱，若 x无右孩子，则必有左孩子，这个左孩子就是无右孩
49、子，则必有左孩子，这个左孩子就是x的直接的直接 前驱结点。前驱结点。 North China Electric Power University树的遍历树的遍历 由于树种每个结点可以有两棵以上的子树，所以有两种遍由于树种每个结点可以有两棵以上的子树，所以有两种遍历树的方法：历树的方法：1. 先序遍历：先访问树的根结点，然后依次先序遍历树的各棵先序遍历：先访问树的根结点，然后依次先序遍历树的各棵 子树。子树。2. 后序遍历：依次后序遍历树的根的各棵子树，然后访问根结后序遍历：依次后序遍历树的根的各棵子树，然后访问根结 点。点。树没有中序遍历，因为树中树没有中序遍历，因为树中每个结点的子树的个数可
50、以每个结点的子树的个数可以有多个，把根放在那两个子有多个，把根放在那两个子树之间是无法确定的，算法树之间是无法确定的，算法实现上不易统一。实现上不易统一。ABCED先序序列：先序序列：A B C D E后序序列：后序序列：B D C E ANorth China Electric Power University森林的遍历森林的遍历1.先序遍历森林：先序遍历森林： 1）访问森林中第一棵树的根结点；）访问森林中第一棵树的根结点； 2）先序遍历第一棵树中根结点的子树森林；）先序遍历第一棵树中根结点的子树森林； 3）先序遍历除去第一棵树之后剩余的树构成森林。）先序遍历除去第一棵树之后剩余的树构成森林
51、。2.中序遍历森林中序遍历森林 1）中序遍历森林中第一棵树的根结点的子树林；）中序遍历森林中第一棵树的根结点的子树林； 2）访问第一棵树的根结点；）访问第一棵树的根结点； 3）中序遍历除去第一棵树之后剩余的树构成的树林。）中序遍历除去第一棵树之后剩余的树构成的树林。由树和二叉树的转换规则可由树和二叉树的转换规则可知：森林的先序和中序遍历知：森林的先序和中序遍历即为其对应的二叉树的先序即为其对应的二叉树的先序和中序遍历。和中序遍历。ABCDEFGHIJ先序序列：先序序列：ABCDEFGHIJ后序序列：后序序列：BCDAFEHJIGNorth China Electric Power University
