树形表示法与数据结构——从树到哈夫曼编码

"本课件主要涵盖了树形表示法，包括凹入表示法、嵌套集合表示法、广义表表示法，并详细介绍了数据结构中的树和二叉树概念。讲解了树的类型定义、基本术语，如树的根、子树、非线性数据结构的层次关系等。此外，还涉及了二叉树的类型定义、性质、存储结构、遍历方法，线索二叉树的介绍，以及树和森林的关系。最后，讨论了哈夫曼树及其编码的应用。" 在数据结构中，树是一种非常重要的非线性数据结构，它通过分支关系定义了一种层次结构。树的定义包含一个特殊的结点，称为根结点，当树中结点数量大于1时，其他结点被分为多个互不相交的子集，每个子集又构成一个子树，这些子树的根结点与原始根结点有直接的父子关系。 树形表示法包括几种不同的方式： 1. 凹入表示法：通过缩进的方式显示结点的层次关系，例如 `(A(B(E(K,L),F),C(G),D(H(M),I,J)))`。 2. 嵌套集合表示法：用括号将结点组织成嵌套的集合，显示其层次结构，如 `(树根(子树1，子树2，…，子树n))`。 3. 广义表表示法：用列表来表示树的结构，如 `A B C D F E G H I J M K L A B D C E`。 二叉树是树的一个特殊形式，每个结点最多有两个子结点，分为左子结点和右子结点。二叉树的类型定义和性质包括树的空性、度（结点的子结点数量）、叶结点（度为0的结点）和分支结点（度大于1的结点）。二叉树的存储结构通常采用数组或链式结构，如二叉链表。二叉树的遍历有前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）三种方式。 线索二叉树是在二叉链表的基础上增加线索，以便于在非递归情况下进行遍历。树和森林是树的扩展概念，森林是由若干棵树组成的集合。 哈夫曼树（也称为最优二叉树）是一种带权路径长度最短的二叉树，常用于数据压缩，通过构建哈夫曼树可以得到哈夫曼编码，这是一种变长的编码方式，能够有效提高编码效率。 在实际应用中，理解和掌握这些树形表示法和二叉树的概念及操作对于解决许多算法问题至关重要，例如搜索、排序、压缩和文件系统的设计等。