《线索二叉树》PPT课件

《《线索二叉树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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主要内容知识点树和二叉树定义二叉树的性质，存储结构二叉树的遍历及遍历算法的应用**线索二叉树二叉树和树及森林的关系Huffman树与H

2、uffman编码重点难点二叉树的性质及应用二叉树的遍历算法及应用**线索二叉树的算法Huffman树的构造方法树的算法3线索二叉树线索二叉树的提出：1、遍历的实质：非线性结构线性化（前驱、后继）;2、前驱和后继是在遍历中得到的;3、知道前驱和后继，再遍历时就不需要栈;4、可以在二叉链表结构中增加前驱和后继两个指针域;5、n个结点的二叉树有n＋1个空指针，可以利用。4线索二叉树n个结点的二叉链表中含有n+1个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息,这样的指针称为“线索”，加上了线

3、索的二叉链表称为线索链表，加上线索的二叉树就是线索二叉树（ThreadedBinaryTree）。将二叉树变为线索二叉树的过程称为线索化。lchildltagdatartagrchildltag=rtag=5线索二叉树<？序><前驱/后继/全>线索化只有空指针才能加线索6前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID7中序（全）线索二叉树NULLACFEDBNULLA00E11C01D11F11B00NULLA为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的

4、根结点，rchild域指向访问序列的最后一个结点，这样，就建立了一个双向线索链表。8后序（全）线索化9线索链表的类型定义typedefstructBiThrNode{ElemTytedata;structBiThrNode*lchild,*rchild;左、右孩子指针intltag,rtag;}BiThrNode，*BiThrTree后面将讨论以下三方面的算法：一、线索化二、遍历三、查找前驱和后继10算法举例6.7中序线索化BiThrTreepre=null;//设置前驱voidInOrder

5、Threat(BiThrTreeT){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);//

6、右子树中序线索化}}//结束InOrderThreat11算法举例6.8前序线索化BiThrTreepre=null;//设置前驱voidPreOrderThreat(BiThrTreeT){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;//设置前驱的右线索；

7、pre=T;//前驱后移if(T->ltag==0)PreOrderThreat(T->lchild);//左子树前序线索化PreOrderThreat(BT->rchild);//右子树前序线索化}}12算法举例6.9后序线索化BiThrTreepre=null;//设置前驱voidPostOrderThreat(BiThrTreeT){if(T){PostOrderThreat(T->lchild);//左子树后序线索化PostOrderThreat(T->rchild);//右子树后序线索化

8、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;//前驱指针后移}}//结束PostOrderThreat13线索二叉树的中序非递归遍历中序线索二叉树的中序非递归遍历带头结点的中序线索二叉树的中序非递归遍历14算法举例6.