第六章 树和二叉树试卷.ppt

若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 各字符出现概率为{ C:2/18, A:7/18, S:4/18, T:5/18 },化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。 7 2 5 4 0 1 0 0 1 1 A C T S CAST CAST SAT AT A TASA A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于霍夫 曼树的带权路径长度WPL。 霍夫曼编码是一种无前缀 编码(都由叶结点组成,路径 不会重复)。解码时不会混淆。 霍夫曼编码: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 等长编码: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100 霍夫曼编码树 0 0 0 1 1 1 2 4 5 7 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * CreateBiTree(T-leftChild)和T-leftChild=CreateBiTree()区别 * A B C D E F G 孩子表示法(多重链表 ) 第一种解决方案 等数量的链域 (d为树的度) data child1 child2 child3 childd A B C D E F G ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 空链域n(d-1)+1个 第二种解决方案 孩子链表 将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表。 typedef struct CTNode { int child; struct CTNode *next; }*ChildPtr; typedef struct{ TElemType data; ChildPtr firstchild; }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n,r;//结点数和根的位置 }CTree; A B C D E F G 0 A 1 B 2 C ^ 3 D 4 E ^ 5 F ^ 6 G ^ 1 2 3 ^ 4 5 ^ 6 ^ 结点结构 data firstChild nextSibling A B C D E F G 空链域n+1个 树的左子女-右兄弟表示 （二叉链表表示） B C D G F E ? ? ? ? ? ? ? A ? typedef char TreeData; typedef struct node { TreeData data; struct node *firstChild, *nextSibling; } TreeNode; typedef TreeNode * Tree; 用左子女-右兄弟表示实现的树定义 T1 T2 T3 T1 T2 T3 A F H B C D G I J E K A F B C D E G H I K J A B C E D H I K J F G 3 棵树的森林 各棵树的二叉树表示 森林的二叉树表示 森林与二叉树的转换 树的二叉树表示: 树的遍历 深度优先遍历 先根次序遍历 后根次序遍历 A B C D E F G A B C E D G F 深度优先遍历 当树非空时 {访问根结点 依次先根遍历根的各棵 子树} 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 A B C E D G F 树的先根次序遍历 A B C D E F G 树的后根次序遍历: 当树非空时 {依次后根遍历根的各棵 子树 访问根结点} 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBC