DS06-树树和二叉树.ppt

森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 构造Huffman树的方法——Huffman算法 构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树 max=(hl，hr); return(max+1); } else return(0); } 在中根遍历的线索树中查找前驱结点 对于二叉树中任意结点p，要找其前驱结点,当p-Ltag=1时，p-Lchild即为p的前驱结点；当p-Ltag=0时，说明p有左子树，此时p的中根遍历下的前驱结点即为其左子树右链下的最后一个结点。 Void Previous(ThreadTnode * p, ThreadTnode *pre) { ThreadTnode *q; if(p-Ltag==1) pre= p-Lchild; else { for(q= p-Lchild;q-Rtag==0;q=q-Rchild); pre=q; } } 在中根遍历的线索树中查找后继结点 二叉树中任意结点p，若要找其后继结点，当p-Rtag=1时，p-Rchild即为p的后继结点；当p-Rtag=0时，说明p有右子树，此时p的中根遍历下的后继结点即为其右子树左链下的最后一个结点。 Void Succedent(ThreadTnode *p, ThreadTnode *succ) { ThreadTnode *q; if (p-Rtag==1) ? succ= p- RChild; else { for(q= p-RChild; q-Ltag==0 ;q=q-LChild ); succ=q; } } 6.4 树和森林 树的存储结构 双亲（链表）表示法 用一组连续的存储空间（数组）来存储树中的结点，每个数组元素中不但包含结点本身的信息，还保存该结点双亲结点在数组中的下标号。数组中每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 在双亲表示法下，树的数据类型定义如下：#define Maxsize 50typedef struct Node{DataType data;int parent;}Tnode;Tnode Ptree[Maxsize]; a b c d e f h g i a c d e f g h i b －1 1 2 2 3 5 5 5 1 6 0 1 2 3 4 5 7 8 data parent 如何找孩子结点 孩子链表表示法 把每个结点的孩子结点排列起来，构成一个单链表，该单链表就是本结点的孩子链表。具有n个结点的树就形成了n个孩子链表 孩子结点 #define Maxsize 50 typedef struct ChildNode { int Child; struct ChildNode * next; }ChildNode; 表头结点 typedef struct { DataType data; ChildNode * ChildHead ; }DataNode; 孩子链表 DataNode Ctree[Maxsize]; 孩子兄弟链表表示法 又称为二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）。 FirstChild data Nextsibling typedef struct CSNode { DataType data; Struct CSNode *FirstChild, *Nextsibling; } *CSTree; 对应 结论：树的孩子兄弟链表表示法与对应二叉树的二插链表表示法相同。因此，上图中的树与二叉树之间存在相互转换的关系。 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空 树转换为二叉树 加线：在树中所有相邻的兄弟之间加一连线； 抹线：对树中每个结点，除了其左孩子外