小竞 (编辑)
计算机科学中最常见且最有趣的数据结构之一是树结构。就像一棵普通的树一样，树结构有叶子和分支。但是还涉及到节点，以及父节点、子节点和兄弟节点——有点像家谱。
树的相互连接性在表示数据方面具有一些独特的优势。还有各种用于树的操作和算法，其中一些是专门用于树的。在本文中，我们将深入探讨树的结构以及它们的用途示例。
树数据结构是什么？
树结构非常类似于现实生活中的树。元素由节点表示，节点通过边缘或分支连接。这导致了一种层次结构，节点在节点下方形成，被称为子节点，而顶部节点称为父节点。
没有父节点的顶部节点是根节点，没有自身子节点的子节点称为兄弟节点。
通过以这种方式连接节点，我们可以表示数据之间的关系并对其进行逻辑组织。这对于说明逐步过程或相互关联的事件非常有帮助。节点可以分支的程度取决于树的类型，树的类型有很多种。
有哪些类型的树？
最常见的类型是二叉树、平衡树和一般树。二叉树每个节点只能有两个子节点，就像二进制只有两个数字一样。堆树是二叉树的一个子类型，用于实现堆或优先队列。
它们具有堆属性，其中节点的值要么大于或等于子节点的值，要么小于或等于子节点的值，这取决于它是最大堆还是最小堆树。
平衡树在左右分支上具有相同的高度，而一般树可以有任意数量的子节点。
除了这些类型，还有n叉树、b树、堆树、四叉树和八叉树：
- n叉树类似于一般树，但在每种情况下被限制在n个子节点。自然地，它们用于表示具有不同层次的关系。
- b树也被称为自平衡树，当插入或删除元素时，它们会重新调整节点以保持平衡结构。这些通常用于需要快速访问大型数据集的情况，例如数据库和文件系统。
- 四叉树和八叉树非常独特，因为它们用于分别表示2维和3维空间。它们通过将区域分割成四分之一和八分之一，分别表示空间中的矩形或长方体区域。因此，它们用于表示空间数据。
树数据结构使用了哪些操作？
树与线性数据结构共享许多常见操作，例如插入、删除和遍历。然而，树还有一些独特的操作。
这些操作包括搜索操作、高度和深度计算、子树操作、平衡操作、计数操作以及序列化和反序列化。下表中简要描述了这些操作，以及它们的常规语法。
| 操作 | 描述 | 语法 |
|---|---|---|
| 插入 | 根据树的规则添加一个新的节点 | insert（key，value）; 这将插入一个具有特定键和特定值的节点 |
| 删除 | 从树中删除一个节点，同时保持其属性 | delete（key） |
| 搜索 | 根据键或值在树中找到特定的节点 | search（key） |
| 遍历 | 以某种顺序访问树中的每个节点，通常是中序遍历，前序遍历或后序遍历 | inorder（node），preorder（node），postorder（node） |
| 高度/深度 | 计算树的高度/深度，即根节点和最后一个叶节点之间的边数 | height（） |
| 子树 | extractsubtree（node）其中节点是根节点; mergesubtrees（tree1，tree2）其中tree1和tree2是要合并的子树 | 包括旋转，重新排序或重新平衡以保持平衡的树 |
| 计数 | 计算节点数 | size（） |
| 平衡 | 包括旋转，重新排序或重新平衡以保持平衡的树 | balance（） |
| 序列化 | 将树转换为线性表示，准备传输 | serialize（root）其中root是根节点 |
| 反序列化 | 从线性序列重构树 | deserialize（serializedtree）其中serializedtree是序列 |
树数据结构的遍历方法
值得注意的是，您有三种常见的遍历树的方法。它们是：
- 中序遍历 – 先递归访问左子树，然后访问根节点，最后访问右子树，按升序排列。可用于创建排序元素列表。
- 前序遍历 – 先访问根节点，然后按顺序访问左子树和右子树。由于遍历顺序的自然特性，可以用于创建树，或者与dfs（深度优先搜索）算法一起使用。
- 后序遍历 – 先访问左子树和右子树，然后访问根节点。常用于树的删除。
与树数据结构一起使用的算法
现在我们已经介绍了各种树操作，让我们继续介绍可以与它们一起使用的算法。主要算法在下表中概述。
| 算法 | 描述 |
|---|---|
| dfs | 深度优先搜索：在移动到下一个分支之前，尽可能深地遍历节点。 |
| bfs | 广度优先搜索：在移动到下一个深度级别之前，尽可能广泛地遍历树。 |
| huffman编码 | 构建二叉树以便压缩数据。 |
如果您想了解更多关于这些特定算法及其工作原理的信息，请查阅我们的有关dfs，bfs和huffman编码的文章。
树数据结构的实际应用
在这个阶段，只有实际演示这些操作才有意义。首先，我们将演示如何使用这些操作来进行一个简单的二叉树示例。考虑下面这段python代码：
class node:
def __init__(self, key):
self.key = key
self.left = none
self.right = none
class binarysearchtree:
def __init__(self):
self.root = none
def insert(self, key):
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if node is none:
return node(key)
if key node.key:
node.right = self._insert_recursive(node.right, key)
return node
def delete(self, key):
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, node, key):
if node is none:
return node
if key node.key:
node.right = self._delete_recursive(node.right, key)
else:
if node.left is none:
return node.right
elif node.right is none:
return node.left
else:
successor = self._find_min(node.right)
node.key = successor.key
node.right = self._delete_recursive(node.right, successor.key)
return node
def _find_min(self, node):
current = node
while current.left is not none:
current = current.left
return current
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
if node is none or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)
def inorder(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
if node is not none:
self._inorder_recursive(node.left)
print(node.key)
self._inorder_recursive(node.right)
def height(self):
return self._height_recursive(self.root)
def _height_recursive(self, node):
if node is none:
return 0
left_height = self._height_recursive(node.left)
right_height = self._height_recursive(node.right)
return max(left_height, right_height) + 1
def size(self):
return self._size_recursive(self.root)
def _size_recursive(self, node):
if node is none:
return 0
return self._size_recursive(node.left) + self._size_recursive(node.right) + 1
bst = binarysearchtree()
bst.insert(5)
bst.insert(3)
bst.insert(8)
bst.insert(2)
bst.insert(4)
print("inorder traversal:")
bst.inorder()
print("height of the tree:", bst.height())
print("size of the tree:", bst.size())
print("searching for key 3:", bst.search(3))
bst.delete(3)
print("inorder traversal after deleting key 3:")
bst.inorder()代码解释
这是一段相当长的代码块，但非常有效地展示了这些操作。
我们首先定义“node”类和构造方法“__init__”。该方法以节点的“key”参数作为参数，并将其分配给节点的key属性。最初，节点没有左或右子节点，正如下面的代码所示。
接下来，我们声明“binarysearchtree”类及其构造方法，因为我们使用了二叉树数据结构。根属性“root”初始化为none，因为树是空的。
插入和删除
然后我们定义“insert”方法和递归方法，它接受当前节点参数和要插入的节点的键作为参数。我们然后有代码将节点插入到左侧和右侧分支，大于当前节点的节点插入到右侧，反之亦然。
类似地，“delete”也是如此，它以相同的方式检查节点的值。一旦当前节点的键等于要删除的键，该节点就会被删除。如果节点有子节点，则找到其后继节点并用其替换。
查找和搜索
然后定义“find_min”，它是搜索操作的一种变体，用于找到具有最小键的节点。然后我们定义“search”，它在找到匹配的节点之前递归使用。
遍历
在此之后，我们有“inorder”遍历方法。其他遍历的实现方式类似，但节点遍历的顺序不同。在所有情况下，节点参数表示当前节点。
高度
然后是“height”方法。遍历树的两个分支，然后从中计算高度。
计数
接下来使用“count”或“size”。遍历并计数树，并加上1以计算我们起始的节点。
创建树
最后，我们创建一个二叉树“bst”。我们向树中插入5个键，执行中序遍历，并打印高度、大小和一个搜索节点。最后，我们删除键3，并再次打印遍历结果以反映此变化。结果可以在下面的图像中看到。
树的创建结果。
©jingzhengli.com
总结
总而言之，树是一种非常灵活的层次结构，常用于其有效的插入、删除和搜索操作。每棵树都有一个根节点、子节点和兄弟节点，以及连接节点的分支。
二叉树是最常见的树类型之一，但还有平衡树、n叉树、四叉树、八叉树和一般树。在计算机和数据科学中，层次关系很常见，因此理解如何实现和操作树结构将成为您项目中宝贵的工具。
本文顶部显示的图像为©song_about_summer/shutterstock.com。
