树的遍历和哈夫曼树.ppt

北京化工大学信息学院 数据结构 数据结构 北京化工大学 信息科学与技术学院计算机系 史晟辉 shishenghui@ shish@ 树的特点 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 二叉树的顺序表示 二叉树遍历 二叉树遍历的递归算法 二叉树遍历的应用 二叉树遍历的非递归算法 二叉树遍历 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 二叉树遍历 中序遍历结果： a + b * c - d - e / f 前序遍历结果： - + a * b - c d / e f 后序遍历结果： a b c d - * + e f / - 二叉树遍历的应用 二叉树遍历的应用 二叉树遍历的应用 以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。 计算二叉树结点个数的递归算法 将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中 从完全二叉树的顺序表示转换为二叉链表表示 二叉树的计数 例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 求构造的二叉树。 前序序列 { ABHFDECKG } 中序序列 { HBDFAEKCG } 树与森林 用双亲表示实现的树定义 用左子女-右兄弟表示实现的树定义 树的遍历 深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历 树的先根次序遍历 当树非空时 访问根结点 依次先根遍历根的各棵子树 树的后根次序遍历 当树非空时 依次后根遍历根的各棵 子树 访问根结点 树的广度优先(层次次序)遍历 哈夫曼树 (Huffman Tree) 哈夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 哈夫曼树的定义 线索二叉树 给出二叉树，画出对应的中序线索化二叉树。 Thanks. 5 2 7 4 6 11 Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 3 11 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 p1 p2 5 5 1 4 i 5 2 7 4 6 11 Weight parent leftChild rightChild 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 3 11 -1 1 4 18 -1 -1 -1 0 1 2 3 4 5 6 p1 p2 6 6 0 5 i 18 建立哈夫曼树的算法 void CreateHuffmanTree ( HuffmanTree T,