《线索二叉树》PPT课件.ppt

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