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