20147 S6.4线索二叉树 §6.4线索二叉树 1. 基本概念 ·结点结构 基本概念 lchd lue dats rtag rehild ◆中序线索树中必有两个指针域为空 。线索标志左标志ag o:lchild为左指针，指向孩子 中序序列 开始结点，左线索为NUL】 中序为对称序 :Ichild为左线索，指向前墅 终端结点，右线煮为NULL (0:rchild为右指针，指向孩子 开始结点为最左下的结点] 右标志rtag 中序序列 终端结点为最右下的结点 :hd为右线索，指向后继 。中序线索树和中序线索链表中序序列：CBDAFHGIE 前序线索树中，有几个指针域为空☒ 前序序列的开始结点为根，故当它的左子树非空时，其指针域 指向左指子树，此时前序序列开始结点左指针非空， 风" SULL 但是，前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针， (m中序线索二又树 (6)中序线客 §6.4线索二叉树 86.4线索二叉树 1. 基本概念 码学霸对时著鹅茅整锦春帮针老为牌。仅当只有1个根时成根 ◆线索树中，如何判定结点是否为叶子？ lag=tag=1(适用于三种线索树) 有时线索树只有左线索或右线索之一 2 线索化 将二叉树变为线索树的过程 按某种次序遍历，在遍历过程中用线索取代空指针 与前序线索树对称 typedef enum (Link,Thread)PointerTag;∥o为Link,1为Thread 带头结点的线索链表 typedef struct node{ 树上6.11图心以.令空指针也指向此消兵 DataType data; PointerTag Itag,rtag; struct node 'Ichild,'rchild: }BinThrNode,'BinThrTree; 设p和pre分别指向遍历过程中当前访问崎点和其前重，即pre和p是 [折向泽漏瑞点〔一餐) 前宽和后的关系，其中p为全局，在速历过程中立缺： 以中序为例，pre初始为NULL,因为中序前驱对开翰结点是NULL· s6.4线索二叉树 86.4线索二叉树 void InorderThreading(BinThrTree p){ 3 操作加速 pre为全局量，初德为NULL (找某结点p中序线察树中)中序前驱和后继结点 计(p)( InorderThreading(p->Ichild)片左子树棱索化 ①找p的中序后继 ,p->ltag=(p->lchild)?Link:Thread;I左物针非空，量为 i)若p的右子树空，则p->rchild为右线察，直接指向'p的中序后键 ∥Link,否为效康。 i)若p的右子树排空(rtag为0)，则p的中序后蛙必是其右子制中第 p>rtag =(p->rchild)?Link:Thread; 个中序塘历到的销点，其特征是： 简t(pre(∥着pe春在 从的右孩子开，养在装下，真至找测一个没有左孩 许(pre->rtag=Thread)∥当前结点p的前里右标志为能拿 子的结点为止，不坊膏其为右子制中“量左下”的结点： pre>rchild=p; ∥令pe的右镜擦指向中序后接p 计(p>tag=Thread)/当前维点的左镜擦已建立 p>lchild =pre; 冷当前书点的左指向中序前 这里k多1，R不一定是叶子，其右子树可 pre=p;使pre为p的前，量环不变量 为空。可非空。 InorderThreading(p->rchild);右于制线察化 ·算法 ,请自己给出找钟定结点*即的中序后银 算法。时间O),快于无械索的二又树。 。时间：和速历相同0(. 后序前序线家化类做于此， 62014/4/7 6 §6.4 线索二叉树 1. 基本概念  结点结构  线索标志 0 : lchild ltag = 1: lchild 0 : rchild rtag = 1: rchild       为左指针，指向孩子 左标志 为左线索，指向前驱 为右指针，指向孩子 右标志 为右线索，指向后继 31  中序线索树和中序线索链表 中序序列：CBDAFHGIE §6.4 线索二叉树 NULL NULL           开始结点，左线索为 中序序列 中序为对称序 终端结点，右线索为 1. 基本概念  中序线索树中必有两个指针域为空  前序线索树中 有几个指针域为空？       开始结点为最左下的结点 中序序列 终端结点为最右下的结点 32  前序线索树中，有几个指针域为空？ 前序序列的开始结点为根，故当它的左子树非空时，其指针域 指向左指子树，此时前序序列开始结点左指针非空。 但是，前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针。 §6.4 线索二叉树 1. 基本概念  后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根 的右子树为空时有两个空指针。 33 与前序线索树对称  带头结点的线索链表 树上6.11图(b). 令空指针也指向此哨兵    指向终端结点(一般) 线索 指向开始结点(更好，有利于遍历操作) §6.4 线索二叉树 1. 基本概念  线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树)  有时线索树只有左线索或右线索之一 2. 线索化 将二叉树变为线索树的过程 按某种次序遍历，在遍历过程中用线索取代空指针。 34 typedef enum {Link, Thread} PointerTag; // 0为Link，1为Thread typedef struct node { DataType data; PointerTag ltag, rtag; struct node *lchild, *rchild; } BinThrNode, *BinThrTree; 设p和pre分别指向遍历过程中当前访问结点和其前驱，即*pre和*p是 前驱和后继的关系，其中pre为全局量，在遍历过程中建立线索。 以中序为例，pre初始为NULL，因为中序前驱对开始结点是NULL。 §6.4 线索二叉树 void InorderThreading(BinThrTree p) { // pre为全局量，初值为NULL if (p) { InorderThreading(p->lchild); // 左子树线索化 p->ltag = (p->lchild) ? Link : Thread; // 左指针非空，置为 // Link，否则为线索。 p->rtag = (p->rchild) ? Link : Thread; if (pre) { // 若*pre存在 前结点 的前 右标志为线索     访 问 35 if (pre->rtag == Thread) // 当前结点*p的前驱右标志为线索 pre->rchild = p; // 令*pre的右线索指向中序后继*p if (p->ltag == Thread) // 当前结点的左线索已建立 p->lchild = pre; //令当前节点的左线索指向中序前驱 } pre = p; //使*pre为*p的前驱，循环不变量 InorderThreading(p->rchild); // 右子树线索化 } }  时间：和遍历相同O(n). 后序(前序)线索化类似于此。       问根结点 §6.4 线索二叉树 3. 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 ① 找*p的中序后继 i） 若*p的右子树空，则p->rchild为右线索，直接指向*p的中序后继 ii）若*p的右子树非空(rtag为0)，则*p的中序后继必是其右子树中第一 个中序遍历到的结点，其特征是： 从*p的右孩子开始，沿其左链往下找，直至找到一个没有左孩 子的结点为止 不妨称其为右子树中“最左下”的结点 p 36 子的结点为止，不妨称其为右子树中“最左下”的结点。 这里k≥ 1, Rk不一定是叶子，其右子树可 为空，可非空。  算法 请自己给出找给定结点*p的中序后继 算法。时间O(h)，快于无线索的二叉树。 p