当前位置：首页 > article >正文

数据结构：树、森林

article 2024/11/18 23:48:09

二叉树与树结构差异

树（一般树）：树是一种数据结构，其中每个节点可以有任意数量的子节点（除了根节点和叶子节点外）。因此，一般树的节点在数组中的表示并不是那么直接，特别是当树不是完全二叉树时。
二叉树：二叉树是一种特殊的树，其中每个节点最多有两个子节点（通常称为左子节点和右子节点）。这种结构使得二叉树在数组中的表示更加直接和高效，特别是当二叉树是完全二叉树或满二叉树时。

顺序存储的差异：

一般树的顺序存储：对于一般树，由于其子节点的数量不固定，因此很难在数组中直接表示。如果尝试使用顺序存储，可能会导致大量的空间浪费，因为需要为不存在的子节点预留空间。此外，访问子节点和父节点的索引计算也会变得复杂，因为需要额外的数据结构（如指针或索引数组）来跟踪每个节点的子节点位置。
二叉树的顺序存储：对于二叉树，特别是完全二叉树或满二叉树，顺序存储非常高效。每个节点都可以根据其在数组中的索引来直接访问其左子节点和右子节点（通过简单的数学计算）。同样，也可以通过索引计算来找到父节点。这种存储方式不仅节省了空间（因为没有为不存在的子节点预留空间），而且访问速度也很快。

总的来说就是树的顺序存储结构中，数组下标代表结点的编号，下标所存的内容指示了节点之间的关系，而二叉树的数组下标即表示结点的编号又指示了二叉树中各结点之间的关系。

应用场景：

一般树的顺序存储：由于上述的空间浪费和访问复杂性，一般树的顺序存储并不常见。相反，它们更常使用链式存储（如通过指针连接节点），这样可以更灵活地表示任意数量的子节点。
二叉树的顺序存储：二叉树的顺序存储特别适用于完全二叉树或满二叉树，以及那些可以通过某种方式（如旋转或修改）转化为这些特殊类型的二叉树。此外，顺序存储的二叉树在某些特定应用中（如堆排序中的堆结构）也非常有用。

结论：

二叉树和树的顺序存储结构在本质上是相似的，但由于二叉树结构的特殊性，它在顺序存储中更加高效和直接。对于一般树，顺序存储通常不是最佳选择，而链式存储则更为常见和实用。

树和二叉树是两种常见的树形数据结构，它们之间可以相互转换。这种转换在处理树形结构的问题时非常有用，因为二叉树具有一些特殊的性质（如左子树和右子树的明确区分）和高效的算法（如二叉搜索树、堆等）。以下是树和二叉树相互转换的详细过程：

树转换为二叉树

树转换为二叉树的过程通常基于“儿子兄弟表示法”。在这种表示法中，每个节点都有指向其第一个孩子和下一个兄弟节点的指针。在转换为二叉树时，我们可以将节点的第一个孩子视为二叉树的左孩子，将节点的下一个兄弟视为二叉树的右孩子。具体步骤如下：

添加虚根（可选）：如果原树是一个森林（即多棵树），则首先添加一个虚根节点，将森林中的所有树作为这个虚根的子树。这一步是可选的，因为对于单棵树来说，不需要添加虚根。
转换过程：
- 对于树中的每个节点，将其第一个孩子节点作为二叉树的左孩子。
- 将该节点的下一个兄弟节点（即与其共享同一父节点的下一个节点）作为二叉树的右孩子。
- 递归地对每个子树执行上述操作。
去除虚根（如果添加了）：在转换完成后，如果添加了虚根，则将其去除，得到最终的二叉树。

二叉树转换为树

二叉树转换为树的过程是上述转换的逆过程。具体步骤如下：

恢复兄弟关系：
- 从二叉树的根节点开始，遍历整棵树。
- 对于每个节点，如果它存在右孩子，则将该右孩子视为原树中其左孩子的下一个兄弟节点。
- 注意，在二叉树中，一个节点的左孩子和右孩子分别对应原树中的第一个孩子和下一个兄弟节点。
递归处理：
- 对二叉树的每个子树递归执行上述操作，以恢复整棵树的兄弟关系。
结果：最终得到的是一棵或多棵树的集合（如果原二叉树是由多个树的根节点组成的森林转换而来）。

注意事项

在转换过程中，需要确保不会破坏原树或二叉树的结构。
转换后的树或二叉树应保留原树的所有节点和边。
如果原树是森林，则在转换为二叉树时需要添加虚根；在转换回树时，如果添加了虚根，则需要将其去除。

通过上述过程，我们可以实现树和二叉树之间的相互转换，从而在处理树形结构的问题时更加灵活和高效。

树的遍历

先根遍历：

先访问根节点
再依次访问根结点的每棵子树
与该树对应的二叉树的先序序列相同

后根遍历：

先依次遍历根结点的每棵子树，遍历子树时仍遵循先子树后根的原则
再访问根结点
与该树对应的二叉树的中序序列相同

森林的遍历

先序遍历森林：

对森林中的树一次采用先序遍历

中序遍历森林：

对森林中的树依次采用后根遍历

树与二叉树的应用：

哈夫曼树（Huffman Tree）

又称最优二叉树，是一种具有特殊性质的二叉树结构。其定义及相关术语如下：

定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树的性质：

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
哈夫曼树的结点总数为2N-1，其中N为初始结点数（也即叶结点数）。
哈夫曼树中不存在度为1的结点（即每个非叶结点都有两个子结点）。
哈夫曼树并不唯一，但所有可能的哈夫曼树的WPL必然相同且为最优。

哈夫曼编码：

基于哈夫曼树的一种数据压缩方法。通过对数据中的字符进行频率统计，构建哈夫曼树，并根据树的结构为字符分配不同的编码（通常是二进制编码），从而实现数据的压缩。哈夫曼编码有静态和动态两种形式，分别适用于不同的应用场景。

哈夫曼编码和定长编码：

哈夫曼编码是一种非常有效的数据压缩编码。由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。然后，将从根到叶结点的路径上分支标记的字符事作为该字符的编码。

这棵哈夫曼树的 WPL 为
WPL =1x45+3x(13+12+16)+4x(5+9)=224
此处的 WPL 可视为最终编码得到二进制编码的长度，共224位。若采用3位固定长度编码，则得到的二进制编码长度为300位，因此哈夫曼编码共压缩了25％的数据。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。