数据结构（陈仲民）CH6next.PPTVIP

6.4线索二叉树 定义： 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~ 线索：指向前驱或后继结点的指针称为~ 线索二叉树：加上线索的二叉链表表示的二叉树叫~ 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~ 实现 在有n个结点的二叉链表中必定有n+1个空链域 在线索二叉树的结点中增加两个标志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驱 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后继 结点定义： Void inThreading(ThreadTree root) { p=root; If (p) { InThreading(p-lc);左子树 if(!p-lc) 可建前驱线索 { p-lt=1; p-lc=pre;} if (! Pre-rc)可建后继线索 { pre-rt=1; pre-rc=p;} pre=p;保持pre指向p的前驱 InThreading(p-rc);右子树 } } Void Inorder-Thr(Threadtree Head) { Threadtree p=Head-lc; while (p!=Head) { while (p-lt==0) p=p-lc; 找第一个结点 printf(“%d”,p-data); 访问 while(p-rt==1 p-rc!=Head) 可直接访问后继 { p=p-rc; printf(“%d”,p-data); } p=p-rc;转右子树 } return; } 孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易 破坏了树的层次 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 链式存储结构 二叉链表 6.5树与二叉树转换 森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 6.5.3 树和森林的遍历 树的遍历 遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列 常用方法 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点 6.6二叉树的应用 哈夫曼树(Huffman)——带权路径长度最短的树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~ 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度：树中所有带权结点的路径长度之和 构造Huffman树的方法——Huffman算法 构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树 * typedef struct Threadnode { enum{0,1} lt, rt; ElemType data; struct Threadnode *lc, *rc; }ThreadTNode, *ThreadTree; lc lt data rt rc A B C D E A B D C E T 先序序列：ABCDE 先序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 A B C D E