c语言描述的树及二叉树pdf

### C语言描述的树及二叉树知识点解析 #### 一、树的定义与运算 **树的定义：** 树是一种非线性的数据结构，它是由一个或多个节点组成的有限集合，这些节点之间存在一种层次关系。具体来说，树可以定义为包含n (n≥0)个结点的有限集合T。 1. **空树**：当n = 0时，该树为空树。 2. **非空树**：当n > 0时，树中存在一个唯一的根结点（Root），其余结点被划分为m (m>0)个互不相交的有限集T1, T2, …, Tm，每个集合本身又是一棵树，称为根结点的子树（Subtree）。 **示例：** - 只有一个根结点的树 - 一般的树 **树的其他表示方法：** 1. **集合表示法**：通过集合的形式表示树的结构。 2. **嵌套区间法**（括号表示法）：使用括号来表示树的层次结构。 3. **凹入表示法**（章节表示法）：采用类似目录结构的方式展示树的层次。 **基本术语：** 1. **结点的度**：结点的子树的数量。 2. **树的度**：树中所有结点的度的最大值。 3. **终端结点**（叶子结点）：度为0的结点。 4. **非终端结点**（分支结点）：度不为0的结点。 5. **双亲**与**孩子**结点：结点与其子树根结点之间的关系。 6. **兄弟结点**：拥有相同双亲的结点。 7. **结点的层次**：从根结点开始计算，根结点位于第0层，根结点的孩子位于第1层，依此类推。 8. **树的深度**：树中结点的最大层次。 9. **有序树**与**无序树**：根据结点的子树是否有固定顺序区分。 10. **森林**：由m (m≥0)棵互不相交的树组成。 **树的基本运算：** 1. 初始化：`InitiateTree(T)` 2. 销毁：`DestroyTree(T)` 3. 创建：`CreateTree(T, definition)` 4. 求双亲结点：`Parent(T, p)` 5. 求最左孩子结点：`LeftChild(T, p)` 6. 求右兄弟结点：`RightSibing(T, p)` 7. 插入子树：`InsertChild(T, p, i, c)` 8. 删除子树：`DeleteChild(T, p, i)` 9. 遍历树：`TraverseTree(T, visit())` #### 二、二叉树 **二叉树的定义：** 二叉树也是一种非线性数据结构，由n (n≥0)个结点组成。二叉树的每个结点最多有两个子结点，分别称为左子结点和右子结点。二叉树可以为空，也可以由一个根结点及其两个互不相交的子树（左子树和右子树）组成。 **二叉树的形态：** 1. 空二叉树 2. 仅有根结点的二叉树 3. 右子树为空的二叉树 4. 左子树为空的二叉树 5. 左右子树均非空的二叉树 **二叉树的基本运算：** 1. 初始化：`InitiateBiTree(T)` 2. 销毁：`DestroyBiTree(T)` 3. 创建：`CreateBiTree(T, definition)` #### 三、二叉树的遍历策略及算法 **二叉树的遍历：** 二叉树的遍历是指按照一定的顺序访问二叉树中的所有结点，使得每个结点恰好被访问一次。主要的遍历策略包括： 1. **前序遍历**（Preorder Traversal）：先访问根结点，然后递归地遍历左子树，最后递归地遍历右子树。 2. **中序遍历**（Inorder Traversal）：先递归地遍历左子树，然后访问根结点，最后递归地遍历右子树。 3. **后序遍历**（Postorder Traversal）：先递归地遍历左子树，然后递归地遍历右子树，最后访问根结点。 **非递归遍历算法：** 为了实现非递归遍历算法，通常需要借助栈这种辅助数据结构来跟踪遍历过程中的节点。例如，在前序遍历时，先将根结点压入栈中，然后不断取出栈顶元素并访问之，同时将其右子结点和左子结点按相反顺序压入栈中。这一过程一直持续到栈为空为止。 #### 四、二叉树的线索化 **线索化概念：** 线索二叉树是对二叉树的一种特殊处理方式，目的是使二叉树的遍历无需使用递归算法。在原二叉树的基础上，将空指针域利用起来，指向该结点的前驱或后继结点。 **线索二叉树的构建：** 1. 前驱线索：当前结点的左子结点指针指向其前驱结点。 2. 后继线索：当前结点的右子结点指针指向其后继结点。 #### 五、树、森林与二叉树的转换 **转换方法：** 1. 将森林转换为二叉树：每棵树的根结点连接成一条链表，并将每棵树的第一个孩子作为根结点的左子结点，其余孩子作为右子结点。 2. 将二叉树转换为森林：对于二叉树中的每个结点，如果它的左子结点为空，则它是一个树的根结点；如果左子结点不为空，则继续向下查找直到找到根结点。 #### 六、哈夫曼树及其应用 **哈夫曼树简介：** 哈夫曼树是一种特殊的二叉树，用于编码问题。它的构造原则是根据给定的一组字符及其出现频率，构造出一棵带权路径长度最小的二叉树。 **构建哈夫曼树的步骤：** 1. 将给定的字符及其出现频率作为叶子结点，构造n棵初始的二叉树。 2. 选取两棵根结点权值最小的二叉树合并为一棵新的二叉树，新树的根结点的权值为其两棵子树根结点的权值之和。 3. 重复上一步，直至只剩下一棵树，即为哈夫曼树。 **哈夫曼编码：** 哈夫曼编码是一种最优前缀编码，通过对哈夫曼树进行遍历得到每个字符的编码，通常左子树对应0，右子树对应1。 **哈夫曼树的应用：** 1. 数据压缩：通过哈夫曼编码实现高效的数据压缩。 2. 文件传输：在网络通信中，通过哈夫曼树进行数据编码，提高传输效率。 3. 信息检索：在文本搜索等信息检索领域，利用哈夫曼树进行高效索引。 通过以上分析可以看出，树和二叉树是非常重要的数据结构，它们在计算机科学的许多领域都有着广泛的应用。理解这些基本概念和技术不仅可以帮助我们更好地解决实际问题，还可以为进一步学习更高级的数据结构和算法奠定坚实的基础。