数据结构第六章 树和二叉树.ppt

《数据结构第六章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章 树和二叉树.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章树和二叉树树和二叉树6.1 树的类型定义树的类型定义6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储结构二叉树的存储结构6.4 二叉树的遍历二叉树的遍历6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 树和森林的遍历树和森林的遍历6.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码一、树的定义一、树的定义 树是树是n（n0）个结点的有限个结点的有限集。当集。当n=0时称为空树；在任意一时称为空树；在任意一棵非空树中，有且仅有一个称为根棵非空树中，有且仅有一个称为根的结点，其余的结点可分为的结点，其余的结点可分为m(m 0)个互不相交的有限集个互不相交的有限集T1,

2、T2,Tm,其中每一个集合又称其中每一个集合又称为一棵树，并且称为根的子树。同为一棵树，并且称为根的子树。同理，每一棵子树又可以分为若干个理，每一棵子树又可以分为若干个互不相交的有限集互不相交的有限集6.1 树的类型定义树的类型定义ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后

3、继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不个互不相交的有限集相交的有限集T1,T2,Tm，其中每一棵子集本其中每一棵子集本身又是一棵符合本定义的树，称为根身又是一棵符合本定义的树，称为根root的子树。的子树。数据关系数据关

4、系 R：二、抽象数据类型树的定义二、抽象数据类型树的定义ADT Tree 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类ADT Tree Root(T)/求树的根结点求树的根结点 查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(

5、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)/删除结点删除结点p的第的第

6、i棵子树棵子树 树的树的结点结点：包含一个数据元素：包含一个数据元素 及若干个指向其子及若干个指向其子 树的分支；树的分支；结点的度结点的度：一个结点拥有的子树数目；：一个结点拥有的子树数目；树的度树的度：一棵树上所有结点度的最大值；：一棵树上所有结点度的最大值；叶子结点叶子结点（终端结点）：度为零的结点；终端结点）：度为零的结点；分支结点分支结点（非终端结点）（非终端结点）：度大于零的结点；：度大于零的结点；(从根到结点的从根到结点的)路径路径：由从根到该结点所经分支和由从根到该结点所经分支和 结点构成；结点构成；三、基本术语三、基本术语DHIJM 孩子结点孩子结点：结点的子树的根称为该结点

7、的孩子结点；：结点的子树的根称为该结点的孩子结点；双亲结点双亲结点：相应地，该结点称为孩子的双亲结点；：相应地，该结点称为孩子的双亲结点；兄弟兄弟：具有同一父结点的子结点互称兄弟；：具有同一父结点的子结点互称兄弟；堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟；：其双亲在同一层的结点互为堂兄弟；祖先结点祖先结点：从根到该结点所经分支上的所有结点；：从根到该结点所经分支上的所有结点；子孙结点子孙结点：以某结点为根的子树中任一结点都称为：以某结点为根的子树中任一结点都称为 该结点的子孙；该结点的子孙；ABCDEFGHIJMKL 结点的结点的层次层次：从根结点到该结点所经过的路径长度：从根结点到该结点

8、所经过的路径长度加加1；树的树的深度深度：树中叶子结点具有的最大层次数；：树中叶子结点具有的最大层次数；有序树有序树：如果将树中结点的各子树看成从左至右是：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树；有次序的（即不能互换），则称该树为有序树；第一个孩子第一个孩子：在有序树中，最左边的子树的根称为：在有序树中，最左边的子树的根称为第一个孩子；第一个孩子；最后一个孩子最后一个孩子：最右边：最右边的子树的根称为最后一个的子树的根称为最后一个孩子；孩子；ABCDEFGHIJMKL 森林森林：是：是m(m 0)棵互不相交的树的集合。对树棵互不相交的树的集合。对树中每个结

9、点而言，其子树的集合即为森林。中每个结点而言，其子树的集合即为森林。任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=（root，F）其中：其中：root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林ArootBCDEFGHIJMKLF树树T的结点总数的结点总数n(n0)等于其所有结点的出度之等于其所有结点的出度之和加和加1。深度为深度为K的树（的树（K叉树）第叉树）第i(i 1)层至多有层至多有Ki-1个个结点。结点。深度为深度为h的的k(k1)叉树至多有叉树至多有 个结点。个结点。具有具有n个结点的个结点的k叉树的最小深度为叉树的最小深度为logk(n(k-1)

10、+1)。树的性质树的性质一、二叉树的定义一、二叉树的定义 二叉树是二叉树是n(n0)n(n0)个结点的有限集合，个结点的有限集合，这个集合或是空集，或是由一个根结点以及两这个集合或是空集，或是由一个根结点以及两棵互不相交的、被称为根的左子树和右子树所棵互不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。组成；左子树和右子树分别又是一棵二叉树。特点特点：每个结点至多只有两棵子树，每个结点至多只有两棵子树，且二叉树的子树有左右之分，其次且二叉树的子树有左右之分，其次序不能任意颠倒。序不能任意颠倒。6.2 二叉树的类型定义二叉树的类型定义ABCDEFGHK根结点左子树右子树

11、二、二叉树的五种基本形态：二、二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树三、二叉树的主要基本操作：三、二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类 Root(T)/求根函数；求根函数；Value(T,e);/求结点函数；求结点函数；Parent(T,e);/求双亲函数；求双亲函数；LeftChild(T,e)或或RightChild(T,e);/求孩子结点函数；求孩子结点函数；LeftSibling(T,e)或或RightSibling(T,e);/求兄弟函数；

12、求兄弟函数；BiTreeEmpty(T);/树判空函数；树判空函数；BiTreeDepth(T);/求树深度函数；求树深度函数；PreOrderTraverse(T,Visit();/先序先序遍历操作遍历操作 InOrderTraverse(T,Visit();/中序遍历操作中序遍历操作 PostOrderTraverse(T,Visit();/后序遍历操作后序遍历操作 LevelOrderTraverse(T,Visit();/层序遍历操作层序遍历操作 查找类：查找类：InitBiTree(&T);/构造空的二叉树；构造空的二叉树；Assign(T,&e,value);/结点赋值函数结点赋值

13、函数 CreateBiTree(&T,definition);/建树函数；建树函数；InsertChild(T,p,LR,c);/插入子树操作；插入子树操作；插入类插入类ClearBiTree(&T);/将二叉树置为空树将二叉树置为空树DestroyBiTree(&T);/销毁二叉树销毁二叉树DeleteChild(T,p,LR);/删除子树操作删除子树操作删除类删除类 性质性质 1：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。(i1)四、二叉树的重要特性：四、二叉树的重要特性：ABDEFHJMKL第2层第3层第4层 i=1 时，只有一个根结点，显然时，只有一个

14、根结点，显然2 i-1=20=1 正确；正确；假设对所有的假设对所有的 j，1 j i，命题成立，即命题成立，即第第j层上至多有层上至多有2 j-1个个结点。那么可以证明结点。那么可以证明j=i时命题也成立。时命题也成立。用归纳法证明用归纳法证明：由归纳假设：第由归纳假设：第i-1层上至多有层上至多有2 i-2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结点数层上的最大结点数的的2倍，即倍，即2*2 i-2=2 i-1性质性质 2：深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k

15、-1 个结点（个结点（k1）。）。证明：证明：基于上一条性质，深度为基于上一条性质，深度为 k 的二叉的二叉树上的结点数至多为树上的结点数至多为 20+21+2k-1=2k-1。性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数二叉树上分支总数 b=n1+2n2除根结点之外，其余结点都有一个分支进入，所以除根结点之外，其余结点都有一个分支进入，所以 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。两类两类特殊特殊的二叉树：的

16、二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点 的二叉树。123456789 10 11 12 13 14 15特点特点:每一层上的结点数都是最大结点数。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。abcdefghij特点特点:叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；对任意结点，若其右分支下的子孙的最大层次对任意结点，若其右分支下的子孙的最大层次为为L L，则其左分支下的子孙的最大层次必为则其左分支下的子孙的最大层次必为L L或或L+1 L+1；性质性质 4：具有 n 个结点的完全二

17、叉树的深度深度为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。6.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序 存储表示存储表示 用一组地址连续的存储单元依次自上而下、自用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于一般二左至右存储完全二叉树上的结点元素。对于一

18、般二叉树，则应将其每个结点与完全二叉树上的结点相叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。对照，存储在一维数组的相应分量中。1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7完全二叉树完全二叉树 一般二叉树一般二叉树1234578 910 11 1261234567一、一、二叉树的顺序存储表示二叉树的顺序存储表示#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;二、二叉

19、树的链式存储表示二、二叉树的链式存储表示1.二叉链表二叉链表2三叉链表三叉链表3双亲链表双亲链表4线索链表线索链表ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表含有两个指针域的结点结构含有两个指针域的结点结构typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:ADEBCF root2

20、三叉链表三叉链表parent lchild data rchild结点结构结点结构:含有三个指针域的结点结构含有三个指针域的结点结构 typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针左右孩子指针 struct TriTNode *parent;/双亲指针双亲指针 TriTNode,*TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:ABCDEFG二叉树二叉树ABCDEFGroot二叉链表二叉链

21、表BCDEFGA root三叉链表三叉链表一、一、问题的提出问题的提出二、二、先左后右的遍历算法先左后右的遍历算法三、三、算法的递归描述算法的递归描述四、四、中序遍历算法的非递归描述中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例6.4 二叉树的遍历二叉树的遍历 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出 “访问访问”的含义可以很广，可以对结点作各种处理，如：输出结点的信息等。“遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要

22、另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍存在如何遍历历即按什么样的搜索路径搜索路径遍历的问题。对对“二二叉叉树树”而而言言，可可以以有三条搜索路径：有三条搜索路径：1先上后下先上后下的按层次遍历；2先左先左(子树)后右后右(子树)的遍历；3先右先右(子树)后左后左(子树)的遍历。二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：-+/e*afb-cd先序：

23、先序：-+a*b-cd/ef 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：-+/e*afb-cd中序：中序：a+b*c-d-e/f 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：-+/e*afb-cd后序：后序：abcd-*+ef/-三、算法的递归描述三、算法的递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树先序遍历二叉树 if(T)vis

24、it(T-data);/访问结点访问结点 Preorder(T-lchild,visit);/遍历左子树遍历左子树 Preorder(T-rchild,visit);/遍历右子树遍历右子树 void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树中序遍历二叉树 if(T)Inorder(T-lchild,visit);/遍历左子树遍历左子树 visit(T-data);/访问结点访问结点 Inorder(T-rchild,visit);/遍历右子树遍历右子树 void Postorder(BiTree T,void(*visit)(TEle

25、mType&e)/后序遍历二叉树后序遍历二叉树 if(T)Preorder(T-lchild,visit);/遍历左子树遍历左子树 Preorder(T-rchild,visit);/遍历右子树遍历右子树 visit(T-data);/访问结点访问结点 递归算法简明精练，但效率较低。递归算法简明精练，但效率较低。在非递归算法中要用栈来保存遍历过程在非递归算法中要用栈来保存遍历过程中经历的结点的左孩子和右孩子。中经历的结点的左孩子和右孩子。使用栈来实现中序遍历二叉树的基本思使用栈来实现中序遍历二叉树的基本思想：从二叉树的根结点开始，沿左子树一直想：从二叉树的根结点开始，沿左子树一直走到末端为止，

26、在向前搜索的过程中将所遇走到末端为止，在向前搜索的过程中将所遇结点进栈，待遍历完左子树时，从栈顶退出结点进栈，待遍历完左子树时，从栈顶退出结点并访问，然后再遍历右子树。结点并访问，然后再遍历右子树。四、遍历二叉树的非递归算法四、遍历二叉树的非递归算法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&e)Stac

27、k*S;t=GoFarLeft(T,S);/找到最左下的结点找到最左下的结点 while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);else if(!StackEmpty(S)/栈不空时退栈栈不空时退栈 t=Pop(S);else t=NULL;/栈空表明遍历结束栈空表明遍历结束 /while/Inorder_I 五五、遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)

28、4 4、建立二叉树的存储结构、建立二叉树的存储结构1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数对叶子结点计数 CountLeaf(T-lchild,count);CountLe

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

30、thval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;3、复制二叉树、复制二叉树(后序遍历后序遍历)其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rpt

31、r)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);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)new

32、rptr=CopyTree(T-rchild);/复制右子树复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;/CopyTreeABCDEFGHK D C B H K G F E A例如：下列二叉树例如：下列二叉树的复制过程如下：的复制过程如下：newT4、建立二叉树的存储结构、建立二叉树的存储结构 不同的定义方法相应地有不同不同的定义方法相应地有不同的存储结构的建立算法的存储结构的建立算法 以字符串的形式以字符串的形式 根根-左子树左子树-右子树右子树 定义一棵二叉树定义一棵二叉树例如例如

33、:ABCD以空白字符“”表示A(B(,C(,),D(,)空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点生成根结点 CreateBiTree(T-lchild);/构造左子树构造左子树 CreateBiTree(T-rchild);/构造右子树构造右子树 return OK;/CreateBiTre

34、eA B C D A BCD上页算法执行过程举例如下：上页算法执行过程举例如下：ATBCD 仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树;由二叉树的由二叉树的先先(或或后后)序和序和中中序序列建树序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列例例:已知一棵二叉树的先序遍历序列为已知一棵二叉树的先序遍历序列为 ABECDFGHIJABECDFGHIJ

35、，中序遍历序列为中序遍历序列为 EBCDAFHIGJEBCDAFHIGJ，试构造这棵二叉树试构造这棵二叉树 若已知二叉树的先序和中序（或中序和后序）序列，即可构造唯一的二叉树。AEBCDF HI G JAFBEC DHIGJHGDCEFBAIJABFEGCJDH I先序遍历序列为先序遍历序列为 ABECDFGHIJ中序遍历序列为中序遍历序列为 EBCDAFHIGJ6.5 线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？一、一、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是遍历二叉树的结果是:求得结点的一个线性序

36、列。求得结点的一个线性序列。ABCDEFGHK例如:先序序列先序序列: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方法一方法一：在每个结点上增加两个指针域在每个结点上增加两个指针域fwd和和bkwd，分别指示结点在任一次序遍历时得到分别指示结点在任一次序遍历时得到的前驱和后继信息。的前驱和后继信息。显然，这样做使得结构的存储密度大大显然，这样做使得结构的存储密度大大降低。降低。方法二方法二：在有在有n个结点的二叉链表中必定存在个结点的二叉链表中必定存在n+1个空链域，利用这些空链域来存放结点的前个空链

37、域，利用这些空链域来存放结点的前驱和后继的信息。驱和后继的信息。指向该线性序列中的指向该线性序列中的“前驱前驱”和和“后继后继”的指针，称作的指针，称作“线索线索”例如：例如：A B C D E F G H K D C B E 与其相应的二叉树，与其相应的二叉树，称作称作“线索二叉树线索二叉树”包含包含“线索线索”的存储结的存储结构，称作构，称作“线索链表线索链表”对对线索链表线索链表中结点的约定：中结点的约定：在二叉链表的结点中增加两个标志域增加两个标志域LTag 和和RTag，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域LTag的

38、值为“指针指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志域LTag的值为“线索线索 Thread”。若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域RTag的值为“指针指针 Link”；否则，rchild域的指针指向其“后继”，且右标志域RTag的值为“线索线索 Thread”。如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线线索链表索链表”。对二叉树以某种次序遍历使其变为线索对二叉树以某种次序遍历使其变为线索二叉树的过程，叫做二叉树的过程，叫做线索化线索化。typedef struct BiThrNod TEle

39、mType data;struct BiThrNode *lchild,*rchild;/左右指针左右指针 PointerThr LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerThr;/Link=0:指针，指针，Thread=1:线索线索lchilddatarchildrtagltag结点结构结点结构其中：其中：0 lchild域指示结点的左孩子域指示结点的左孩子1 lchild域指示结点的前趋域指示结点的前趋0 rchild域指示结点的右孩子域指示结点的右孩子1 rchil

40、d域指示结点的后继域指示结点的后继ltag=rtag=-+/e*afb-cd中序序列：中序序列：a+b*c-d-e/f中序线索二叉树中序线索二叉树010-00+01 a 10*00/01 e 11 f 11 b 10-01 c 11 d 1thrt中序线索中序线索链表：链表：二、线索链表的遍历算法二、线索链表的遍历算法:for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如例如:对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历的第一个结点？中序遍历的第一个结点？在中序线索

41、化链表中结点的后继？在中序线索化链表中结点的后继？左子树上处于“最左下最左下”(没有左子树)的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)/T指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点指向根结点 /中序遍历二叉线索树中序遍历二叉线索树T的非递归算法，的非递归算法，/对每个数据元素调用函数对每个数据元素调用函数visit p=T-lchild;/p指向根结点指向

42、根结点 while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;Visit(p-data);/访问第访问第一个结点一个结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结访问后继结点点 p=p-rchild;/p进至其右子树根进至其右子树根 /InOrderTraverse_Thr 线索化的实质是将二叉链表中的空指针改线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时

43、才能得到。因此，线索化的过息只有在遍历时才能得到。因此，线索化的过程即为在遍历过程中修改空指针的过程。为了程即为在遍历过程中修改空指针的过程。为了记下遍历过程中访问结点的先后关系，记下遍历过程中访问结点的先后关系，附设一附设一个指针个指针pre,并始终保持指针并始终保持指针pre指向当前访问指向当前访问的、指针的、指针p所指结点的前驱。由此可得中序遍所指结点的前驱。由此可得中序遍历建立中序线索化链表的算法。历建立中序线索化链表的算法。三、如何建立线索链表？三、如何建立线索链表？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