树和二叉树讲义资料.ppt

第六章 树和二叉树 6.1 树的概念及术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 哈夫曼树及其应用 树的基本术语 证明：对于具有n个结点的二叉链表共有2n个链域，但仅有n-1个非空链域。 所以空链域数＝2n-（n-1) 先序遍历 (Preorder Traversal) 先序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 二叉树遍历应用 以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点先序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。 后继：结点标志为1时，其右指针为其后继；结点标志为0时，其右子树最左下结点为其后继。 用左孩子-右兄弟表示实现的树定义 树的先根遍历 当树非空时 {访问根结点 依次先根遍历根的各棵 子树} 树先根遍历 A B E F C D G 树的后根遍历 当树非空时 {依次后根遍历根的各棵 子树 访问根结点} 树后根遍历 E F B C G D A 赫夫曼树 带权路径长度达到最小的二叉树即为赫夫曼树。 在哈夫曼树中，权值大的结点离根最近。 赫夫曼树的定义 森林进行先序遍历的序列为：A B C D E F G H I J 森林的先序遍历即为其对应的二叉树的先序遍历。 B A D C B A C D H G I J J H G I E F E F 二、中序遍历森林 若森林非空，则可按下述规则遍历之： (1) 中序遍历森林中第一棵树的根结点的子树森林； (2) 访问第一棵树的根结点； (3) 中序遍历除去第一棵树之后剩余的树构成的森林。 森林的遍历 森林进行中序遍历的序列为 B C D A F E H J I G 森林的中序遍历即为其对应的二叉树的中序遍历。 B A D C B A C D H G I J J H G I E F E F 带权路径长度 (Weighted Path Length, WPL) 二叉树的带权 (外部) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。 6.6 赫夫曼树及其应用 (a) WPL=7×2 + 5×2 + 2×2 + 4×2 =36 (b) WPL=7×3 + 5×3 + 2×1 + 4×2 =46 (c) WPL=7×1 + 5×2 + 2×3 + 4×3 =35 其中（c）树的带权路径长度最小， 可以验证，它恰为哈夫曼树。 a b c d 7 a b 5 2 4 c a b 4 d 2 a b 7 5 a 7 a b 5 b c d 2 4 (a) (b) (c) (1) 由给定的n个权值 {w0, w1, w2, …, wn-1}，构造具有n棵二叉树的森林 F={ T0, T1, T2, …, Tn-1 }，其中每棵二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。 赫夫曼算法 - - / + * a b c d e f 遍历结果 a + f * e b - / c - d 先序遍历二叉树的递归算法 void PreOrder( BinTreeNode *T ) { if ( T != NULL ) { Visit( T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); } }// PreOrder - - / + * a b c d e f 遍历结果 a + f b e * - / c - d 中序遍历二叉树的递归算法 void Inorder( BinTreeNode *T ) { if ( T != NULL ) { InOrder ( T-leftChild ); Visit( T-data); InOrder ( T-righ