数据结构第14讲-线索树与树和森林.ppt

1、第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用,6.3.2 线索二叉树,1.何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。,2.线索链表中结点的结构,在二叉链表的结点结构中增加两个标志域，并规定：,其中： LTag =,0 lchild 域指示结点的左孩子

2、 1 lchild 域指示结点的前驱,RTag =,0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后继,二叉树二叉线索存储表示,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索 typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; / 左右孩子指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,3.线索二叉树图例,线索二叉树及其存储结构 （a）

3、中序线索二叉树 （b）中序线索链表,如何在线索树中找结点的后继？,结合中序线索树 若其右标志为“1”，右链是线索，右链直接指示了结点的后继； 若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。,如何在线索树中找结点的前驱？,结合中序线索树 若其左标志为“1”，左链为线索，直接指示其前驱； 若其左标志为“0”，左子树中最右下的结点为其前驱。,线索链表的中序遍历算法 Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) ) /T指向头结点，头结点的左链lchild指向根结点，中序遍历 /二叉线索树T的非递归算法，对每个数

4、据元素调用函数Visit。 p = T-lchild; /p指向根结点 while (p != T) /空树或遍历结束时，p = = T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点 while (p-RTag=Thread / IOTraver_T,4.如何建立线索化链表？,由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。,对二叉链表p进行中序线索化的递归算法(带头结点),

5、Status InOrderThreading(BiThrTree 调用不带头结点的中序线索化的递归算法; 3.最后一个结点线索化（指向头结点）,void InThreading(BiThrTree p) if (p) InThreading(p-lchild); /左子树线索化 if (!p-lchild) p-lchild=pre; p-ltag=Thread; /前驱线索 if (!pre-rchild)pre-rchild=p;pre-rtag=Thread; /后继线索 pre = p; /保持pre指向p的前驱 InThreading(p-rchild); /右子树线索化 InTh

6、reading,对二叉链表p进行中序线索化的递归算法(不带头结点),Status InOrderThreading(BiThrTree ,Status InOrderThreading(BiThrTree /空树，Thrt回指自身,Thrt,Link,Thread,1,else Thrt-lchild=T;/头结点的lchild指向二叉链表根 pre=Thrt; /pre指向前驱结点 InThreading(T);/中序线索化二叉链表T pre-rchild=Thrt;pre-rtag=Thread; /最后一个结点线索化 Thrt-rchild=pre; return OK; ,Thrt,p

7、re,输出：B C A E D,1,0,1,1,1,1,1,0,0,0,0,pre,P=null,T,A,B,D,E,C,F,G,例：对下图的树按先序、后序、中序线索化,第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.6 赫夫曼树及其应用,6.4.1 树的存储结构,三种常用的链表结构： 双亲表示法 孩子表示法 孩子兄弟表示法,1. 双亲表示法 即以一组连续空间存储树的结点， 同时在每个结点中附设一个指示器 指示其双亲结点在链表中的位置。,树

8、的双亲表存储表示 #define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 Elem data; int parent; / 双亲位置域 PTNode; typedef struct /树结构 PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,分析： 这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，Parent(T,x）操作可在常量时间内实现。反复调用Parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。,2. 孩子表

9、示法 由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：,采用第一种格式 多重链表中的结点是同构的，其中 dx 为树的度。由于树中很多结点的度小于 dx ，所以链表中有很多空链域，造成空间浪费。,采用第二种格式 多重链表中的结点是不同构的，其中 dy 为结点的度，drgee 域的值同 dy ，此时可以节省存储空间，但操作不方便。,有没有既能节省空间 又操作方便的办法呢？,另一种方式 把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则 n个结点有 n 个孩子链表（叶子的孩子链表为空

10、)。而 n 个头指针又组成一个线性表，为便于查找，采用顺序存储结构。,树的孩子链表存储表示 typedef struct CTNode /孩子结点 int child; struct CTNode *next; *ChildPtr; typedef struct /双亲结点结构 Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox; typedef struct /树结构: CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,分析： 与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用

11、于Parent(T，x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。,3. 孩子兄弟表示法 或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。,3. 孩子兄弟表示法 例：,树的二叉链表（孩子 - 兄弟）存储表示 typedef struct CSNode Elem data; struct CSNode *firstchild , *nextsibling; CSNode, *CSTree;,分析： 这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(pare

12、nt)域，则同样能方便地实现Parent(T,x)操作。,6.4.2 森林和二叉树的转换,1. 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。,树转换为二叉树方法：,1）对每个孩子进行从左到右的排序； 2）在兄弟之间加一条连线； 3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 4）以根结点为轴心，将整个树顺时针转45。,2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。 若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系

13、。,已知条件：森林和二叉树的对应关系设 森 林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m); 二叉树 B =( LBT, Node(root), RBT ); 由森林转换成二叉树的转换规则为: 若 F = ，则 B = ; 否则，由 Root( T1 ) 对应得到 Node(root); 由 (t11, t12, , t1m ) 对应得到 LBT; 由 (T2, T3, Tn ) 对应得到 RBT。 由二叉树转换为森林的转换规则为: 若 B = , 则 F = ; 否则，由 Node(root) 对应得到 Root( T1 ); 由LBT

14、 对应得到 ( t11, t12, ，t1m);T1除根以外所 构成的森林 由RBT 对应得到 (T2, T3, , Tn)；除T1之外的森林,6.4.3 树和森林的遍历,1. 树的遍历：有三条搜索路径 先根(序)遍历：若树不空，则先访问根结点， 然后依次先根遍历各棵子树。 后根(序)遍历：若树不空，则先依次后根遍历 各棵子树，然后访问根结点。 按层次遍历： 若树不空，则自上而下自左至 右访问树中每个结点。,例 对树进行先根遍历，获得的先根序列是： 对树进行后根遍历，获得的后根序列是：,A B E F C D G H I,E F B C G H I D A,2.森林的遍历,先序遍历(对森林中的

15、每一棵树进行先根遍历) 1）若森林不空，访问森林中第一棵树的根结点； 2）先序遍历森林中第一棵树的子树森林； 3）先序遍历森林中(除第一棵树外)其余树构成的森林。 后序遍历(对森林中的每一棵树进行后根遍历) 1）若森林不空，后序遍历森林中第一棵树的子树森林； 2）访问森林中第一棵树的根结点； 3）后序遍历森林中(除第一棵树外)其余树构成的森林。,例： 对森林进行先序遍历，获得的先序序列是： 对森林进行后序遍历，获得的后序序列是：,B E F C D G H I,E F B C G H I D,总结： 1. 二叉树的线索化 2. 树的表示及其遍历操作； 3. 建立森林与二叉树的对应关系。 由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操作计算机中的