第9周树和二叉树（下）第4讲- 线索二叉树.pdf

对于对于具有具有n个节点的二叉树，采用二叉链存储结构时，每个节点个节点的二叉树，采用二叉链存储结构时，每个节点 有两个指针域，总共有有两个指针域，总共有2n个指针个指针域。域。 其中只有其中只有n- -1个节点被有效指针所个节点被有效指针所指向，即有指向，即有n- -1个非空指针域。个非空指针域。 所以共有所以共有2n- -(n- -1) = n+1个空链域个空链域。 回顾：回顾： 采用某种方法遍历二叉树的结果是一个节点的采用某种方法遍历二叉树的结果是一个节点的线性序列线性序列。 修改空修改空链域链域改为存放改为存放指向指向节点的前趋和节点的前趋和后继节点的地址。后继节点的地址。 这样的指向该线性序列中这样的指向该线性序列中的“前趋”的“前趋”和“后继”的指针，和“后继”的指针，称称 作作线索线索（thread）。 创建创建线索的过程称为线索的过程称为线索化。线索化。 线索化的线索化的二叉树称为线索二叉树。二叉树称为线索二叉树。 显然线索二叉树与采用的显然线索二叉树与采用的遍历方法相关，有遍历方法相关，有先序先序线索二叉树、线索二叉树、 中中序序线索二叉树和后线索二叉树和后序序线索二叉树线索二叉树。 线索二叉树的目的是提高线索二叉树的目的是提高该遍历过程该遍历过程的效率。的效率。 相关概念：相关概念： 在在节点的存储结构上增加节点的存储结构上增加两个标志位两个标志位来区分这两种情况：来区分这两种情况： ltaglchilddatarchildrtag 左标志左标志ltag 0 表示表示lchild指向左孩子节点指向左孩子节点 1 表示表示lchild指向前趋节点，即指向前趋节点，即左左线索线索 这样这样，每个节点的存储结构如下：每个节点的存储结构如下： 右标志右标志rtag 0 表示表示rchild指向右孩子节点指向右孩子节点 1 表示表示rchild指向后继指向后继节点节点， 即即右右线索线索 为了方便算法设计，为了方便算法设计，在线索二叉树中再增加在线索二叉树中再增加一个头节点一个头节点。 typedef struct node ElemType data;/节点数据域节点数据域 int ltag,rtag;/增加的线索标记增加的线索标记 struct node *lchild;/左孩子或线索指针左孩子或线索指针 struct node *rchild;/右孩子或线索指针右孩子或线索指针 TBTNode;/线索树节点类型定义线索树节点类型定义 线索线索化化二叉树中节点二叉树中节点的的类型类型定义如下定义如下： 0 A0 1 E1 0 C0 1 F1 0 B1 1 D1 1 G1 0 / 1 中序中序线索线索二叉树二叉树 （在线索二叉树中在线索二叉树中 再增加一个头节点再增加一个头节点 ） 建立某种次序的线索建立某种次序的线索二叉树二叉树过程：过程： 以以中序线索二叉树中序线索二叉树为例，讨论建立线索二叉树的算法。为例，讨论建立线索二叉树的算法。 以该遍历方法遍历一棵二叉树。以该遍历方法遍历一棵二叉树。 在遍历的过程中，检查当前访问节点的左、右指针域是否为空：在遍历的过程中，检查当前访问节点的左、右指针域是否为空： 如果左指针域为空，将它改为指向前趋节点的线索；如果左指针域为空，将它改为指向前趋节点的线索； 如果右指针域为空，将它改为指向后继节点的线索。如果右指针域为空，将它改为指向后继节点的线索。 CreatThread(b)算法算法：对以二叉链存储的二叉树：对以二叉链存储的二叉树b进行中进行中 序线索化序线索化，并返回线索化后头节点的指针并返回线索化后头节点的指针root。 Thread(p)算法：算法：对以对以*p为根节点的二叉树子树的中序线为根节点的二叉树子树的中序线 索化索化。 建立中序线索二叉树的建立中序线索二叉树的算法算法 p总是总是指向指向当前线索当前线索化的节点化的节点。 pre作为全局变量作为全局变量，指向刚刚访问过的节点指向刚刚访问过的节点。 *pre是是*p的中序前的中序前趋节点趋节点，*p是是*pre的中序后继的中序后继节点节点。 在中序遍历中在中序遍历中: : 中序序列的前趋节点中序序列的前趋节点 pre 中序序列的后继节点中序序列的后继节点 p 若若rchild为为NULL， 改为后继线索改为后继线索 若若lchild为为NULL， 改为前趋线索改为前趋线索 0 A0 1 E1 0 C0 1 F1 0 / 1 0 B1 1 D1 1 G 1 中序中序序列序列： 中序线索中序线索化演示化演示 中序线索树建立完毕中序线索树建立完毕 pre p D G B A E C F p=NULL TBTNode *pre;/全局变量全局变量 TBTNode *CreatThread(TBTNode *b)/中序线索化二叉树中序线索化二叉树 TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode); /创建头节点创建头节点 root-ltag=0; root-rtag=1; root-rchild=b; if (b=NULL) root-lchild=root;/空二叉树空二叉树 else root-lchild=b; pre=root;/pre是是*p的前趋节点的前趋节点,供加线索用供加线索用 Thread(b);/中序遍历线索化二叉树中序遍历线索化二叉树 pre-rchild=root;/最后处理最后处理,加入指向头节点的线索加入指向头节点的线索 pre-rtag=1; root-rchild=pre;/头节点右线索化头节点右线索化 return root; void Thread(TBTNode */左子树线索化左子树线索化 if (p-lchild=NULL)/前趋线索化前趋线索化 p-lchild=pre; p-ltag=1; /建立当前建立当前节点节点的前趋线索的前趋线索 else p-ltag=0; if (pre-rchild=NULL)/后继后继线索化线索化 pre-rchild=p;pre-rtag=1;/建立前趋节点建立前趋节点的后继线索的后继线索 else pre-rtag=0; pre=p; Thread(p-rchild);/递归调用右子树线索化递归调用右子树线索化 中 序 遍 历 ( 递 归 ) 算 法 遍历遍历某种次序的线索某种次序的线索二叉树，就是二叉树，就是从该次序下的从该次序下的开始节点开始节点出发，出发， 反复找到该节点在该次序下的后继节点，反复找到该节点在该次序下的后继节点，直到头节直到头节点。点。 A BC DE G F 以中序线索二叉树为例，开始节点是根节点的最左下节点。以中序线索二叉树为例，开始节点是根节点的最左下节点。 TBTNode *p=tb-lchild; /p指向根节点指向根节点 while (p-ltag=0) p=p-lchild; 开始节点开始节点 在中序线索二叉树中，开在中序线索二叉树中，开 始节点的左指针域为线索，始节点的左指针域为线索， 即即ltag=1 找开始节点的算法：找开始节点的算法： 在中序线索在中序线索二叉树中中序遍历的过程：二叉树中中序遍历的过程： p指向根节点；指向根节点； while p root时循环时循环 找找开始节点开始节点*p； 访问访问*p节点；节点； while (*p节点有节点有右线索右线索) 一直一直访问下去；访问下去； p转向右孩子节点；转向右孩子节点； 0 A0 1 E1 0 C0 1 F1 0 B1 1 D1 1 G1 0 / 1中序线索二叉树的中序中序线索二叉树的中序 遍历遍历示例演示示例演示 D G B AE C F 遍历完毕遍历完毕 中序中序序列序列： p 右指针不是右指针不是线索，线索， 转向转向右孩子右孩子 右指针是右指针是线索，线索， 沿着线索访问沿着线索访问 操作：操作： 找开始节点找开始节点 void ThInOrder(TBTNode *tb) TBTNode *p=tb-lchild;/p指向根节点指向根节点 while (p!=tb) while (p-ltag=0) p=p-lchild;/找开始节点找开始节点 printf(%c,p-data);/访问开始节点访问开始节点 while (p-rtag=1 printf(%c,p-data); p=p-rchild; 如果是线索就一直访问下去 优点：优点：中序遍历算法既没有递归也没有用中序遍历算法既没有递归也没有用栈栈，空间效率，空间效率得到提高。得到提高。 本讲完本讲完