[理学]第五章 树2.ppt

第五章 树 线索二叉树的定义 线索：指向前驱或后继结点的指针称为线索 线索二叉树：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树 定义 将二叉树变为线索二叉树的过程为线索化 算法 二叉树中根序线索化 时间复杂度为：O(n) 查找某结点*p在指定次序下的前驱和后继结点 中序后继分两种情形 *p的右子树空 即p-rtag为Thread *p的右子树非空 即p-rtag为Link 算法 时间复杂度 该算法的时间复杂度不超过树的高度h，即O(h) 查找指定结点*p的后序前驱结点 若*p的左子树为空,则p-lchild是其前驱线索。如F.H结点 若*p的左子树为非空，则p-lchild不是其前驱线索；若*p的有孩子非空，则其有孩子是*p前驱结点，如*P指向A时，其后续前驱为E结点（B、G结点同理）；若*P无有孩子，则*P的后驱前驱为期左孩子结点，如E结点的后续前驱为F结点。 查找指定结点*p的后序后继结点 若*p是根 ，则五后续后继结点，如*p指向A结点时。 若*p是其双亲的右孩子 ，则其后序后继结点就是其双亲，如*P分别指向D、E、G、I、结点时。 若*p是其双亲的左孩子，但*p无右兄弟 ，则其后序后继就是其双亲结点，如*P指向F结点时。 若*p是其双亲的左孩子，但*p有右兄弟，则其后序后继结点为是其双亲右子树中第一个后续遍历到的结点。它应是该右子树中“最左下的叶子节点”，如当*P指向B结点时，其后序后继结点为H. 结论： 线索使得查找中序前驱和中序后继变得简单有效，但对于指定结点的前序前驱和后序后继帮助不大。 遍历中序线索二叉树 算法： 时间复杂性为：O(n) 实现 定义结构数组存放树的结点，每个结点含两个域 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点 找双亲容易，找孩子难 #define MAXNODE //最大结点数 typedef struct { datatype data; //数据域 int parent; //双亲域(静态指针域) }tnode; typedef tnode tree[MAXNODE+1];//静态双亲链表 实现 每个结点的孩子结点(多个)用单链表存储，再用含n个元素的数组指向每个孩子链表 特点 找孩子容易，找双亲难 实现 用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易，破坏了树的层次 类型定义 typedef struct tnodetp { numtype data; tnodetp *fch,*nsib; } * tlinktp; 森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 先根序遍历 A，B，D，E，H，I，J，C，F，G 后根序遍历 D，H，I，J，E，B，F，G，C，A 层次遍历 A，B，C，D，E，F，G，H，I，J 哈夫曼树及其应用 路径 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 树的路径长度 从树根到每一个结点的路径长度之和 树的带权路径长度 树中所有带权结点的带权路径长度之和，记作 WPL＝W1*L1 +W2*L2 +W3*L3 +...+Wn*Ln= 根据给定的n个权值：w1 ,w2 ,...,wn 构成n棵二叉树的集合F＝T1 ,T2 ,...,Tn ，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左、右子树均为空。 在F中任选两棵根结点的权值最小的树作为左、子树构成一棵新的二叉树且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入到F中。 重复做⑵和⑶直到F只含一棵树为止。这棵树便是哈夫曼树。 #define n //叶子数 #define m 2*n-1//树中结点总数 typedef struct //结点类型 { int weight;//权值 int plink,llink,rlink; //双亲及左右孩子指针 }node; node tree[m+1]; //下标取值从1到m，0作为空指针标志 注意 一棵有n个叶子结点的Huffman树有2n-1个结点 初始化 将tree[1..m]中每个结点里的三个指针均置为空(即置为0) 输入 读入n个叶子的权值存于向量的前n个分量中，它们是初始森林中n个孤立的根结点上的权值 合并 对森林中的树共进行n-1次合并，所产生的新结点依次放入向量tree的第i个分量中ni≤m 哈夫曼算法描述 思想 根据字符出现