云大数据结构课程教学课件第6章树和二叉树68.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 森林与二叉树对应关系图示 E F G H J I B A D C F E G I H J A B D C B A D C F E G I H J 树与二叉树对应 树根相连 森林与二叉树对应 * 森林转换成二叉树 如果 是森林，则可按如下规则转换成一棵二叉树B =(root，LB，RB) （1）若F为空，即m = 0，则B为空树； （2）若F为空，即m≠0，则B的根root即为森林中第一棵树的根ROOT( )；B的左子树LB是从 中根结点的子树森林 转换而成的二叉树；其中右子树RB是从森林 转换而成的二叉树。 * 二叉树转换成森林 如果B =(root，LB，RB)是一棵二叉树，则可按如下规则转换成森林 （1）若B为空，则F为空； （2）若B非空，则F中第一棵树 的根ROOT( )即为二叉树B的根root； 中的根结点的子树森林 是由B的左子树LB转换而成的森林；F 中除 之外其余树组成的森林 是由B的右子树RB转换而成的森林。 * 遍历树 一、先根(次序)遍历树 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树； 二、后根(次序)遍历树 　　若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点； * 森林的遍历——先序遍历森林 1. 先序遍历森林 若森林非空，则可按下述规则遍历之 1）访问森林中第一棵树的根结点； 2）先序遍历第一棵树中根结点的子树森林； 3）先序遍历除去第一棵树之后剩余的树构成的森林。 * 先序遍历森林图示 A B D E F G H J I C A B C G D F E H I J * 中序遍历森林 2. 中序遍历森林 若森林非空，则可按下述规则遍历之 1）中序遍历第一棵树的根结点的子树森林； 2）访问第一棵树的根结点； 3）中序遍历除去第一棵树之后剩余的树构成的森林。 * 中序遍历森林图示 A B D E F G H J I C B C D H A E F J I G * 中序遍历森林 void InOrderTraverse_Tree(CSTree T，void(*visit)( CSTree )) { 　　// 以孩子-兄弟链表作存储结构，中序遍历指针T所指森林 　　if (T) {// T=NULL时，森林为空，不做任何操作 　　　InOrderTraverse_Tree(T-firstchild, visit); // 中序遍历*T的子树森林 　　　visit(T); 　　　// 通过函数指针 *visit 访问根结点 　　　InOrderTraverse_Tree(T-nextsibling, visit); // 中序遍历其余树的森林 　　} // if 　} 第六节 赫夫曼树及其应用 * 赫夫曼树基本术语 路径长度 树的路径长度 结点的带权路径长度 树的带权路径长度 D B A E F C 从树中一个结点到另一个结点路径上的分支数目 从树根到每一个结点的路径长度之和 从该结点到树根之间的路径长度与结点上权的乘积 5 6 7 13 16 29 2 7 9 WPS=5×3＋2×3＋9×2＋6×2＋7×2＝65 * 最优二叉树（赫夫曼树）定义 假设有n个权值，试构造一棵有n个叶子结点的二叉树，每个叶子结点为，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。 * 赫夫曼算法 赫夫曼算法——构造赫夫曼树 （1）根据给定的n个权值 构造n棵二叉树的集合F= ，其中每棵二叉树 中只有一个带权为 的根结点，其左右子树均为空。 （2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 （3）在F中删除这两棵树，同时将新得到的二叉树加入F中。 （4）重复（2）和（3），直到F只含一棵树为止。这棵树便是赫夫曼树。 * 赫夫曼算法图示 5 6 2 9 7 7 13 16 29 这棵树便是 赫夫曼树 5 6 2 7 9 * 前缀编码 可以利用二叉树来设计二进制的前缀编码。 假设有一棵如右图所示的二叉树，其四个叶子结点分别表示A、B、C和D四个字符，且约定左分支表示字符‘0’，右