1、第7讲 线索二叉树冯广慧 讲授第6章 树w 6.1 树的概念及操作树的概念及操作w 6.2 二叉树二叉树 n 6.2.1 二叉树的概念及操作二叉树的概念及操作 n 6.2.2 二叉树的性质二叉树的性质n6.2.3 二叉树的存储结构二叉树的存储结构w 6.3 二叉树的遍历二叉树的遍历w 6.4 线索二叉树线索二叉树w 6.5 树和森林树和森林 n6.5.1 树的存储结构树的存储结构 n6.5.2 森林、树、二叉树的相互转换森林、树、二叉树的相互转换 n6.5.3 树和森林的遍历树和森林的遍历w 6.6 哈夫曼树及其应用哈夫曼树及其应用 n 6.6.1 最优二叉树最优二叉树(哈夫曼树哈夫曼树)n
2、6.6.2 哈夫曼编码哈夫曼编码 w*6.7算法设计举例算法设计举例主要内容 w 知识点知识点n树和二叉树定义树和二叉树定义n二叉树的性质，存储结构二叉树的性质，存储结构n二叉树的遍历及遍历算法的应用二叉树的遍历及遍历算法的应用n*线索二叉树线索二叉树n二叉树和树及森林的关系二叉树和树及森林的关系nHuffmanHuffman树与树与HuffmanHuffman编码编码w 重点难点重点难点n二叉树的性质及应用二叉树的性质及应用n二叉树的遍历算法及应用二叉树的遍历算法及应用n*线索二叉树的算法线索二叉树的算法nHuffmanHuffman树的构造方法树的构造方法n树的算法树的算法线索二叉树线索二
3、叉树 线索二叉树的提出：线索二叉树的提出：1、遍历的实质：非线性结构线性化（前驱、遍历的实质：非线性结构线性化（前驱、后继）后继）;2、前驱和后继是在遍历中得到的、前驱和后继是在遍历中得到的;3、知道前驱和后继，再遍历时就不需要栈、知道前驱和后继，再遍历时就不需要栈;4、可以在二叉链表结构中增加前驱和后继两、可以在二叉链表结构中增加前驱和后继两个指针域个指针域;5、n个结点的二叉树有个结点的二叉树有n1个空指针，可以个空指针，可以利用。利用。线索二叉树线索二叉树 n个结点的二叉链表中含有个结点的二叉链表中含有n+1个空指针域，可以利用这个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信
4、息些空指针域来存放结点的前驱和后继的信息,这样的指针称这样的指针称为为“线索线索”，加上了线索的二叉链表称为，加上了线索的二叉链表称为线索链表线索链表，加上线，加上线索的二叉树就是索的二叉树就是线索二叉树线索二叉树（Threaded Binary Tree）。将）。将二叉树变为线索二叉树的过程称为二叉树变为线索二叉树的过程称为线索化线索化。lchildltagdata rtag rchild指向结点前驱指向结点的左孩子lchildlchild:1:0ltag=指向结点后继指向结点的右孩子rchildrchild:1:0rtag=线索二叉树线索二叉树 线索化线索化只有空指针才能加线索只有空指针才
5、能加线索前序前驱线索化前序前驱线索化w 前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID中序（全）线索二叉树中序（全）线索二叉树NULLACFEDBNULLA 00E 11C 01D 11F 11B 00NULLA 为方便起见，在线索链表中增加一个头结点，令其为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，域指向二叉树的根结点，rchild域指向访问序列的最域指向访问序列的最后一个结点，这样，就建立了一个后一个结点，这样，就建立了一个双向线索链表双向线索链表。后序（全）线索化后序（全）线索化AEDCBHGFAEDCBHGFnull线索链表的类型定义
6、typedef struct BiThrNode ElemTyte data;struct BiThrNode *lchild,*rchild;左、右孩子指针左、右孩子指针 int ltag,rtag;BiThrNode，*BiThrTree 后面将讨论以下三方面的算法：后面将讨论以下三方面的算法：一、一、线索化线索化二、遍历二、遍历三、查找前驱和后继三、查找前驱和后继算法举例6.7 中序线索化BiThrTree pre=null;/设置前驱设置前驱void InOrderThreat(BiThrTree T)if(T)InOrderThreat(T-lchild);/左子树中序线索化左子树中
7、序线索化 if(T-lchild=null)T-ltag=1;T-lchild=pre;/左线索为左线索为pre;if(T-rchild=null)T-rtag=1;/置右标记，为右线索作准备置右标记，为右线索作准备 if(pre!=null&pre-rtag=1)pre-rchild=T;/给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 InOrderThreat(T-rchild);/右子树中序线索化右子树中序线索化 /结束结束InOrderThreat 算法举例6.8 前序线索化BiThrTree pre=null;/设置前驱设置前驱void PreOrderT
8、hreat(BiThrTree T)if(T!=null)if(T-lchild=null)T-ltag=1;T-lchild=pre;/设置左线索设置左线索 if(T-rchild=null)T-rtag=1;/为建立右链作准备为建立右链作准备 if(pre!=null&pre-rtag=1)pre-rchild=T;/设置前驱的右线索；设置前驱的右线索；pre=T;/前驱后移前驱后移 if(T-ltag=0)PreOrderThreat(T-lchild);/左子树前序线索化左子树前序线索化 PreOrderThreat(BT-rchild);/右子树前序线索化右子树前序线索化 算法举例6
9、.9 后序线索化BiThrTree pre=null;/设置前驱设置前驱void PostOrderThreat(BiThrTree T)if(T)PostOrderThreat(T-lchild);/左子树后序线索化左子树后序线索化 PostOrderThreat(T-rchild);/右子树后序线索化右子树后序线索化 if(T-lchild=null)T-ltag=1;T-lchild=pre;/左线索为左线索为pre;if(T-rchild=null)T-rtag=1;/置右标记，为右线索作准备置右标记，为右线索作准备 if(pre!=null&pre-rtag=1)pre-rchild
10、=T;/给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 /结束结束PostOrderThreat 线索二叉树的中序非递归遍历w 中序线索二叉树的中序非递归遍历中序线索二叉树的中序非递归遍历w 带头结点的中序线索二叉树的中序非递归带头结点的中序线索二叉树的中序非递归遍历遍历算法举例6.10中序线索二叉树的中序遍历w/遍历即找结点的后继的过程，遍历即找结点的后继的过程，非递归！非递归！w void InorderTraverseThr(BiThrTree p)w while(p)二叉树非空二叉树非空w while(p-ltag=0)找中序序列的开始结点找中序序列的开始结点
11、 p=p-lchild;printf(p-data);w while(p&p-rtag=1)w p=p-rchild;printf(p-data);/找找P的中序后继结的中序后继结点点w if(p)p=p-rchild;/右子树的最左孩子是右子树的最左孩子是p的后继的后继w /whilew InorderTraverseThr算法举例6.11 带头结点的线索二叉树 的中序遍历w/头结点的头结点的lchild域指向二叉树的根结点域指向二叉树的根结点w/rchild域指向访问序列的最后一个结点域指向访问序列的最后一个结点w void InorderTraverseThr(BiThrTree thr
12、t)w p=thrt-lchild;p指向根结点指向根结点w while(p!=thrt)二叉树非空二叉树非空w while(p-ltag=0)找中序序列的开始结点找中序序列的开始结点w p=p-lchild;w printf(p-data);w while(p-rtag=1&p-rchild!=thrt)w p=p-rchild;printf(p-data);/找找P的中序后继结点的中序后继结点w p=p-rchild;w /while(p!=thrt)w InorderTraverseThr线索树上查找前驱和后继w 前序线索树上找前驱和后继前序线索树上找前驱和后继(DLR)w 中序线索树上
13、找前驱和后继中序线索树上找前驱和后继(LDR)w 后序线索树上找前驱和后继后序线索树上找前驱和后继(LRD)前序线索树上找前驱和后继找前驱：找前驱：困难困难找后继（找后继（DLR）：若结点有左子女，则左子女是后继；否则，若结点有左子女，则左子女是后继；否则，rchild指向后继。指向后继。算法举例6.12 前序线索树上找后继BiThrTree PreorderNext(BiThrTree p)if(p-ltag=0)结点有左子女结点有左子女 return(p-lchild);结点的左子女为其前序后继结点的左子女为其前序后继 else return(p-rchild);PreorderNext中
14、序线索树上找前驱和后继 中序的前驱和后继都往上指向祖先中序的前驱和后继都往上指向祖先找前驱：找前驱：若左标记为若左标记为1，则，则lchild指向其前驱；否则，其指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。前驱是其左子树上按中序遍历的最后一个结点。找后继找后继：若右标记为若右标记为1，则，则rchild指向其后继；否则，指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。其后继是其右子树上按中序遍历的第一个结点。算法举例6.13 中序线索树上找前驱BiThrTree InorderPre(BiThrTree p)BiThrTree q;if(p-ltag=1)结点的左
15、子树为空结点的左子树为空 q=p-lchild 结点的左指针域为左线索，指向其前驱结点的左指针域为左线索，指向其前驱 else q=p-lchild;p结点的中序前驱是左子树中最右边结点结点的中序前驱是左子树中最右边结点 while(q-rtag=0)q=q-rchild;if return(q);InorderPre算法举例6.14 中序线索树上找后继BiThrTree InorderNext(BiThrTree p)BiThrTree q;if(p-rtag=1)结点的右子树为空结点的右子树为空 q=p-rchild 结点的右指针域为右线索，指向其后继结点的右指针域为右线索，指向其后继 e
16、lse q=p-rchild;P结点的中序后继是其右子树中最左边结点结点的中序后继是其右子树中最左边结点 while(q-ltag=0)q=q-lchild;if return(q);InorderNext后序线索树上找前驱和后继找前驱找前驱(LRD)：若结点有右子女，则右子女是其前驱；否若结点有右子女，则右子女是其前驱；否则，则，lchild指向其前驱。指向其前驱。找后继找后继：困难，需要知道其双亲。困难，需要知道其双亲。算法举例6.15 后序线索树上找前驱BiThrTree PostorderPre(BiThrTree p)if(p-rtag=0)结点有右子女结点有右子女 return(p
17、-rchild);结点的右子女为其后序前驱结点的右子女为其后序前驱 else return(p-lchild);PreorderPre线索树上结点的插入与删除除修改结点指针外，除修改结点指针外，还需要修改线索。还需要修改线索。请编写在中序全线索二叉树T中的结点P下插入一棵根为X的中序全线索二叉树的算法。如果P左右孩子都存在，则插入失败并返回FALSE；如果P没有左孩子，则X作为P的左孩子插入；否则X作为P的右孩子插入。插入完成后要求二叉树保持中序全线索并返回TRUE。题目要求中序全线索化题目要求中序全线索化T树树P结点的度不结点的度不能是能是2。因此：。因此：1.以以X为根的中序全线索化二叉树
18、只能做为为根的中序全线索化二叉树只能做为P的右子树或左子树插入。的右子树或左子树插入。2.若若X无左（右）子树，要修改无左（右）子树，要修改X的左（右）的左（右）线索；线索；3.若若X有左（右）子树，则修改有左（右）子树，则修改X左左(右右)子树子树上最左结点和最右结点的线索。上最左结点和最右结点的线索。4.还可能要修改原还可能要修改原P结点前驱的右线索或后结点前驱的右线索或后继的左线索。继的左线索。【题目分析】【题目分析】算法设计int TreeThrInsert(BiThrTree T,P,X)在中序全线索二叉树在中序全线索二叉树T的结点的结点P上，插入以上，插入以X为根的中为根的中序全线
19、索二叉树，返回插入结果信息。序全线索二叉树，返回插入结果信息。if(P-ltag=0&P-rtag=0)printf(“P有左右子女，插入失败有左右子女，插入失败n”)；return(0);if(P-ltag=0)P有左子女，将有左子女，将X插为插为P的右子女的右子女 if(X-ltag=1)q=X;记住记住X，后边将，后边将X的左线索的左线索(前驱前驱)修改为修改为P else 寻找寻找X的左子树上按中序遍历的第一个结点的左子树上按中序遍历的第一个结点 q=X-lchild;while(q-ltag=0)q=q-lchild;q-lchild=P;q(指向指向X子树的最左结点子树的最左结点)
20、的左线索的左线索(前驱前驱)是是P if(X-rtag=1)q=X;记住记住X，后边将，后边将X的右线索的右线索(后继后继)修改为修改为P的后继的后继 else 寻找寻找X的右子树上按中序遍历的最后一个结点的右子树上按中序遍历的最后一个结点 q=X-rchild;while(q-rtag=0)q=q-rchild;q-rchild=P-rchild;q(指向指向x的最右结点的最右结点)的右线索的右线索(后继后继)修改为修改为P的后继的后继 if(P-rchild-ltag=1)P-rchild-lchild=q;修改修改P结点后继的左线索结点后继的左线索?P-rtag=0;P-rchild=X
21、;P结点的右子女为结点的右子女为X,右标记置右标记置0 结束了结束了X插为插为P的右子女的右子女 else P无左子女，将无左子女，将X插为插为P的左子女的左子女 if(X-ltag=1)q=X;记住记住X，X无左子女，将无左子女，将P的左线索改为的左线索改为X的左线索的左线索 else X有左子女，找有左子女，找X左子树上按中序遍历的第一个结点左子树上按中序遍历的第一个结点 q=X-lchild;while(q-ltag=0)q=q-lchild;q-lchild=P-lchild;q的左线索的左线索(前驱前驱)是是P的左线索的左线索 if(X-rtag=1)q=X;记住记住X，后边将，后边将X的右线索的右线索(后继后继)修改为修改为P else X有右子树，查其右子树中最右边的结点，将该结点的后继修改有右子树，查其右子树中最右边的结点，将该结点的后继修改为为P q=X-rchild;while(q-rtag=0)q=q-rchild;q-rchild=P;P-ltag=0;P-lchild=X;最后将最后将P的左标记置的左标记置0，P的左子女链接到的左子女链接到X 结束将结束将X插入为插入为P的左子女的左子女 return(1)；插入成功返回插入成功返回true 结束结束Tree Thrfnsert
