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