树是数据结构的分层形式。当我们处理列表、队列和栈时，项目会彼此跟随。但在树中，项目之间存在父子关系。
想象一下树是什么样子的，想象一下一棵树从地上长出来。现在把这个形象从你的脑海中抹去。树通常是向下画的，所以你最好想象一下向下生长的树的根结构。
在每棵树的顶部是所谓的根节点。这是树中所有其他节点的祖先。
树用于许多事情，例如解析表达式和搜索。某些文档类型，如 XML 和 HTML，也可以用树的形式表示。在本章中，我们将介绍树木的一些用途。
在本章中，我们将介绍以下方面：
- 树木的术语和定义
- 二叉树和二叉搜索树
- 树遍历
让我们考虑一些与树相关的术语。
要理解树木，我们首先需要理解它们赖以生存的基本思想。下图包含由字母为a到M的字符节点组成的典型树。
以下是与树关联的术语列表：
- 节点：每个带圆圈的字母代表一个节点。节点是保存数据的任何结构。
- 根节点：根节点是所有其他节点都来自的唯一节点。具有不可区分根节点的树不能视为树。我们树中的根节点是节点 A。
- 子树：树的子树是一棵树，其节点是另一棵树的后代。节点 F、K 和 L 构成由所有节点组成的原始树的子树。
- 度：给定节点的子树数。仅由一个节点组成的树的阶数为 0。根据所有标准，此一棵树节点也被视为一棵树。节点 A 的阶数为 2。
- 叶节点：这是一个度为 0 的节点。节点 J、E、K、L、H、M 和 I 都是叶节点。
- 边缘：两个节点之间的连接。边有时可以将节点连接到自身，使边显示为循环。
- 父：树中有其他连接节点的节点是这些节点的父节点。节点 B 是节点 D、E 和 F 的父节点。
- 子：连接到父节点的节点。节点 B 和 C 是节点 A（父节点和根节点）的子节点。
- 同级：父节点相同的节点都是同级节点。这使节点 B 和 C 成为兄弟节点。
- 级别：节点的级别是来自根节点的连接数。根节点位于级别 0。节点 B 和 C 位于级别 1。
- 树的高度：树的层数。我们的树有 4 米高。
- 深度：节点的深度是从树根到该节点的边数。节点 H 的深度为 2。
我们将从考虑树中的节点和抽象类开始处理树。
就像我们遇到的其他数据结构（如列表和栈）一样，树是由节点组成的。但是组成树的节点需要包含我们前面提到的父子关系的数据。
现在让我们看看如何在 Python 中构建二叉树node类：
class Node:
def __init__(self, data):
self.data = data
self.right_child = None
self.left_child = None 就像在我们以前的实现中一样，节点是数据的容器，并保存对其他节点的引用。作为二叉树节点，这些引用指向左侧和右侧的子节点。
为了测试此类，我们首先创建几个节点：
n1 = Node("root node")
n2 = Node("left child node")
n3 = Node("right child node")
n4 = Node("left grandchild node") 接下来，我们将节点相互连接。我们将n1作为根节点，并将n2和n3作为其子节点。最后，我们将n4作为左子树钩住n2，这样我们在遍历左子树时会得到一些迭代：
n1.left_child = n2
n1.right_child = n3
n2.left_child = n4 一旦我们建立了树结构，我们就可以遍历它了。如前所述，我们将遍历左子树。我们打印出节点，然后沿着树向下移动到左下一个节点。我们一直这样做，直到到达左子树的末尾：
current = n1
while current:
print(current.data)
current = current.left_child 您可能已经注意到，这需要在客户端代码中进行大量工作，因为您必须手动构建树结构。
二叉树是每个节点最多有两个子节点的树。二叉树非常常见，我们将使用它们在 Python 中构建 BST 实现。
下图是以 5 为根节点的二叉树示例：
每个子项都被标识为其父项的右或左子项。由于父节点本身也是一个节点，因此每个节点都将保留对左右节点的引用，即使这些节点不存在。
常规二叉树没有关于元素在树中如何排列的规则。它只满足每个节点最多应有两个子节点的条件。
二叉搜索树（BST）是一种特殊的二叉树。也就是说，它是一棵结构上是二叉树的树。从功能上讲，它是一棵树，它以这样一种方式存储节点，以便能够高效地在树中搜索。
BST 有一个结构。对于具有值的给定节点，左子树中的所有节点都小于或等于该节点的值。此外，此节点的右子树中的所有节点都大于父节点的节点。作为一个例子，考虑下面的树：
这是 BST 的一个示例。在测试我们的树的 BST 属性时，您会发现根节点的左子树中的所有节点的值都小于 5。同样，右子树中的所有节点的值都大于 5。此属性适用于 BST 中的所有节点，没有例外：
尽管前面的图看起来与前面的图相似，但它不符合 BST 的条件。节点 7 大于根节点 5；但是，它位于根节点的左侧。节点 4 位于其父节点 7 的右子树上，这是不正确的。
让我们开始实施 BST。我们希望树包含对其自身根节点的引用：
class Tree:
def __init__(self):
self.root_node = None 这就是保持树状态所需的全部内容。让我们在下一节中检查树上的主要操作。
有一个可用的 BST 需要两个基本的操作。它们是insert和remove操作。这些操作必须遵循一条规则，即它们必须维护赋予 BST 其结构的原则。
在处理节点的插入和移除之前，让我们讨论一些同样重要的操作，这些操作将帮助我们更好地理解insert和remove操作。
BST 的结构使得查找具有最大值和最小值的节点非常容易。
为了找到具有最小值的节点，我们从树的根开始遍历，并在每次到达子树时访问左侧节点。我们采取相反的方法来查找树中具有最大值的节点：
我们从节点 6 向下移动到 3 到 1，以到达具有最小值的节点。同样，我们向下 6，8 到节点 10，这是具有最大值的节点。
找到最小和最大节点的方法同样适用于子树。根节点为 8 的子树中的最小节点为 7。该子树中最大值为 10 的节点。
返回最小节点的方法如下所示：
def find_min(self):
current = self.root_node
while current.left_child:
current = current.left_child
return current while循环继续获取左节点并访问它，直到最后一个左节点指向None。这是一个非常简单的方法。返回最大节点的方法正好相反，此时current.left_child变为current.right_child。
需要Oh才能找到 BST 中的最小值或最大值，其中h是树的高度。
BST 上的操作之一是需要将数据作为节点插入。而在我们的第一个实现中，我们必须自己插入节点，这里我们将让树负责存储其数据。
为了使搜索成为可能，必须以特定的方式存储节点。对于每个给定节点，其左子节点将保存小于其自身值的数据，如前所述。该节点的右子节点将保存大于其父节点的数据。
我们将从数据 5 开始创建一个新的整数 BST。为此，我们将创建一个数据属性设置为 5 的节点。
现在，要添加值为 3 的第二个节点，将 3 与根节点 5 进行比较：
由于 5 大于 3，它将被放在节点 5 的左子树中。我们的 BST 将如下所示：
树满足 BST 规则，其中左子树中的所有节点都小于其父节点。
要将另一个值为 7 的节点添加到树中，我们从值为 5 的根节点开始进行比较：
由于 7 大于 5，因此值为 7 的节点位于该根的右侧。
当我们想要添加一个等于现有节点的节点时会发生什么？我们将简单地将其添加为左节点，并在整个结构中维护此规则。
如果一个节点在新节点所在的位置已经有一个子节点，那么我们必须向下移动树并附加它。
让我们添加另一个值为 1 的节点。从树的根开始，我们对 1 和 5 进行比较：
比较显示 1 小于 5，因此我们将注意力转移到 5 的左侧节点，即值为 3 的节点：
我们将 1 与 3 进行比较，因为 1 小于 3，所以我们将节点 3 下方的标高移动到其左侧。但那里没有节点。因此，我们创建一个值为 1 的节点，并将其与节点 3 的左指针关联，以获得以下结构：
到目前为止，我们只处理只包含整数或数字的节点。对于数字，大于和小于的概念有明确的定义。字符串将按字母顺序进行比较，因此也没有重大问题。但是，如果您想在 BST 中存储自己的自定义数据类型，则必须确保您的类支持排序。
现在，让我们创建一个函数，使我们能够将数据作为节点添加到 BST。我们从函数声明开始：
def insert(self, data): 现在，您将习惯于将数据封装在节点中这一事实。这样，我们将node类隐藏在客户机代码之外，客户机代码只需要处理树：
node = Node(data) 首先检查是否有根节点。否则，新节点将成为根节点（没有根节点的树是不可能的）：
if self.root_node is None:
self.root_node = node
else: 当我们沿着树走下去时，我们需要跟踪我们正在处理的当前节点及其父节点。变量current始终用于此目的：
current = self.root_node
parent = None
while True:
parent = current 这里我们必须进行比较。如果新节点中保存的数据少于当前节点中保存的数据，那么我们将检查当前节点是否有左子节点。如果没有，这就是我们插入新节点的地方。否则，我们将继续遍历：
if node.data < current.data:
current = current.left_child
if current is None:
parent.left_child = node
return 现在我们来处理大于或等于的情况。如果当前节点没有正确的子节点，则新节点将作为正确的子节点插入。否则，我们向下移动并继续查找插入点：
else:
current = current.right_child
if current is None:
parent.right_child = node
return 在 BST 中插入节点需要O（h，其中 h 是树的高度。
BST 上的另一个重要操作是节点的deletion或removal。在此过程中，我们需要考虑三种情况。要删除的节点可能具有以下内容：
- 没有孩子
- 独生子女
- 两个孩子
第一种情况最容易处理。如果要删除的节点没有子节点，我们只需将其与其父节点分离：
因为节点 A 没有子节点，我们将简单地将其与其父节点 Z 分离。
另一方面，当要移除的节点有一个子节点时，该节点的父节点将指向该特定节点的子节点：
为了删除节点 6，它的唯一子节点是节点 5，我们将节点 9 的左指针指向节点 5。必须保留父节点和子节点之间的关系。这就是为什么我们需要注意子节点如何连接到其父节点（即将删除的节点）。将存储已删除节点的子节点。然后，我们将已删除节点的父节点连接到该子节点。
当要删除的节点有两个子节点时，会出现更复杂的情况：
我们不能简单地用节点 6 或 13 替换节点 9。我们需要做的是找到节点 9 的下一个最大的后代。这是节点 12。为了到达节点 12，我们移动到节点 9 的右侧节点。然后向左移动以查找最左侧的节点。节点 12 被称为节点 9 的顺序后继节点。第二步类似于在子树中查找最大节点的移动。
我们将节点 9 的值替换为值 12，然后删除节点 12。在删除节点 12 的过程中，我们以一种更简单的节点删除形式结束，这一点在前面已经讨论过。节点 12 没有子节点，因此我们相应地应用删除没有子节点的节点的规则。
我们的node类没有对父类的引用。因此，我们需要使用 helper 方法来搜索并返回节点及其父节点。此方法类似于search方法：
def get_node_with_parent(self, data):
parent = None
current = self.root_node
if current is None:
return (parent, None)
while True:
if current.data == data:
return (parent, current)
elif current.data > data:
parent = current
current = current.left_child
else:
parent = current
current = current.right_child
return (parent, current) 唯一的区别是，在更新循环中的当前变量之前，我们将其父变量存储为parent = current。实际删除节点的方法从以下搜索开始：
def remove(self, data):
parent, node = self.get_node_with_parent(data)
if parent is None and node is None:
return False
# Get children count
children_count = 0
if node.left_child and node.right_child:
children_count = 2
elif (node.left_child is None) and (node.right_child is None):
children_count = 0
else:
children_count = 1 我们将父节点和找到的节点分别通过行parent, node = self.get_node_with_parent(data)传递给parent和node。了解要删除的节点的子节点数很有帮助。这就是if声明的目的。
在此之后，我们需要开始处理可以删除节点的各种条件。if语句的第一部分处理节点没有子节点的情况：
if children_count == 0:
if parent:
if parent.right_child is node:
parent.right_child = None
else:
parent.left_child = None
else:
self.root_node = None if parent:用于处理 BST 三个节点中只有一个节点的情况。
如果要删除的节点只有一个子节点，if语句的elif部分执行以下操作：
elif children_count == 1:
next_node = None
if node.left_child:
next_node = node.left_child
else:
next_node = node.right_child
if parent:
if parent.left_child is node:
parent.left_child = next_node
else:
parent.right_child = next_node
else:
self.root_node = next_node next_node用于跟踪要删除的节点指向的单个节点的位置。然后我们将parent.left_child或parent.right_child连接到next_node。
最后，我们处理要删除的节点有两个子节点的情况：
...
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data 在查找顺序后继节点时，我们使用leftmost_node = node.right_child移动到右侧节点。只要存在左节点，leftmost_node.left_child将计算为True，并且while循环将运行。当我们到达最左边的节点时，它要么是一个叶节点（意味着它没有子节点），要么是一个右子节点。
我们将要删除的节点更新为顺序后继节点的值node.data = leftmost_node.data：
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else:
parent_of_leftmost_node.right_child = leftmost_node.right_child 前面的语句允许我们将最左侧节点的父节点与任何子节点正确连接。观察等号右侧如何保持不变。这是因为顺序继承人只能有一个正确的孩子作为其唯一的孩子。
remove操作需要O（h），其中 h 是树的高度。
由于insert方法以特定的方式组织数据，我们将按照相同的过程查找数据。在这个实现中，如果找到数据，我们将简单地返回数据；如果没有找到数据，我们将返回None：
def search(self, data): 我们需要从最顶端开始搜索，即在根节点：
current = self.root_node
while True: 我们可能传递了一个叶节点，在这种情况下，树中不存在数据，我们返回None到客户端代码：
if current is None:
return None 我们可能还找到了数据，在这种情况下，我们会返回数据：
elif current.data is data:
return data 根据 BST 中数据存储方式的规则，如果我们正在搜索的数据少于当前节点的数据，我们需要沿着树的左边走：
elif current.data > data:
current = current.left_child 现在我们只剩下一个选项：我们要查找的数据大于当前节点中保存的数据，这意味着我们沿着树向右走：
else:
current = current.right_child 最后，我们可以编写一些客户端代码来测试 BST 的工作方式。我们创建一棵树，并在 1 和 10 之间插入一些数字。然后我们搜索该范围内的所有数字。将打印树中存在的内容：
tree = Tree()
tree.insert(5)
tree.insert(2)
tree.insert(7)
tree.insert(9)
tree.insert(1)
for i in range(1, 10):
found = tree.search(i)
print("{}: {}".format(i, found)) 访问树中的所有节点可以是深度优先或广度优先。这些遍历模式不仅是二叉搜索树所特有的，而且通常是树所特有的。
在这种遍历模式中，我们跟随一个分支（或边）到达其极限，然后向上卷绕继续遍历。我们将使用递归方法进行遍历。深度优先遍历有三种形式，即in-order、pre-order和post-order。
我们中的大多数人可能已经习惯了这种表示算术表达式的方式，因为这是学校通常教我们的方式。在操作数之间插入运算符（中缀），如3 + 4中所示。必要时，可以使用括号构建更复杂的表达式：(4 + 5) * (5 - 3)。
在这种遍历模式下，您将访问左子树、父节点，最后是右子树。
返回树中节点顺序列表的递归函数如下所示：
def inorder(self, root_node):
current = root_node
if current is None:
return
self.inorder(current.left_child)
print(current.data)
self.inorder(current.right_child) 我们通过打印节点并使用current.left_child和current.right_child进行两次递归调用来访问节点。
前缀表示法通常称为波兰语表示法。这里，运算符位于其操作数之前，如+ 3 4中所示。由于优先级没有歧义，因此不需要括号：* + 4 5 - 5 3。
要以预排序模式遍历树，您将按该顺序访问节点、左子树和右子树节点。
前缀符号是 LISP 程序员所熟知的。
此遍历的递归函数如下所示：
def preorder(self, root_node):
current = root_node
if current is None:
return
print(current.data)
self.preorder(current.left_child)
self.preorder(current.right_child) 注意递归调用的顺序。
后缀或反向波兰符号（RPN）将运算符放在其操作数之后，如3 4 +中所示。与波兰语符号的情况一样，运算符的优先级从来没有任何混淆，因此不需要括号：4 5 + 5 3 - *。
在这种遍历模式下，您将访问左子树、右子树，最后是根节点。
post-order方法如下：
def postorder(self, root_node):
current = root_node
if current is None:
return
self.postorder(current.left_child)
self.postorder(current.right_child)
print(current.data)这种遍历从树的根开始，从树的一个级别访问节点到另一个级别：
级别 1 的节点是节点 4。我们通过打印其值来访问此节点。接下来，我们移动到级别 2 并访问该级别上的节点，即节点 2 和节点 8。在最后一级，即第 3 级，我们访问节点 1、3、5 和 10。
这种遍历的完整输出是 4、2、8、1、3、5 和 10。
这种遍历模式是通过使用队列数据结构实现的。从根节点开始，我们将其推送到队列中。队列前面的节点将被访问（退出队列）并打印和存储以供以后使用。左侧节点添加到队列中，然后是右侧节点。因为队列不是空的，所以我们重复这个过程。
该算法的试运行将使根节点 4 排队、出列、访问或访问该节点。节点 2 和 8 排队，因为它们分别是左节点和右节点。节点 2 为了被访问而退出队列。其左侧和右侧节点 1 和 3 排队。此时，队列前面的节点是 8。我们将退出队列并访问节点 8，然后将其左侧和右侧节点排队。因此，该过程将继续，直到队列为空。
算法如下：
from collections import deque
class Tree:
def breadth_first_traversal(self):
list_of_nodes = []
traversal_queue = deque([self.root_node]) 我们将根节点排队，并在list_of_nodes列表中保留访问节点的列表。dequeue类用于维护队列：
while len(traversal_queue) > 0:
node = traversal_queue.popleft()
list_of_nodes.append(node.data) if node.left_child:
traversal_queue.append(node.left_child)
if node.right_child:
traversal_queue.append(node.right_child)
return list_of_nodes 如果traversal_queue中的元素数大于零，则执行循环体。队列前面的节点弹出并附加到list_of_nodes列表中。如果存在左节点，则第一条if语句将enqueue显示node的左子节点。第二条if语句对右侧子节点执行相同的操作。
list_of_nodes在最后一条语句中返回。
现在，我们将简要介绍一下，与使用需要搜索的数据列表相比，BST 是一个更好的想法。假设我们有以下数据集：5、3、7、1、4、6 和 9。使用列表，最坏情况下需要在查找搜索词之前搜索包含七个元素的整个列表：
搜索 9 需要六次跳跃。
对于树，最坏情况是三种比较：
搜索 9 需要两个步骤。
但是，请注意，如果按 1、2、3、5、6、7、9 的顺序将元素插入到树中，那么树的效率不会比列表更高。我们必须首先平衡这棵树：
因此，不仅使用 BST 很重要，而且选择自平衡树有助于改进search操作。
树结构还用于解析算术和布尔表达式。例如，3 + 4的表达式树如下所示：
对于稍微复杂一点的表达式，(4 + 5) * (5-3)，我们将得到以下结果：
现在我们将为用后缀符号编写的表达式建立一个树。然后我们将计算结果。我们将使用一个简单的树实现。为了保持简单，因为我们将通过合并较小的树来生长树，所以我们只需要一个树节点实现：
class TreeNode:
def __init__(self, data=None):
self.data = data
self.right = None
self.left = None 为了构建树，我们将寻求栈的帮助。你很快就会明白为什么。但目前，让我们创建一个算术表达式并设置栈：
expr = "4 5 + 5 3 - *".split()
stack = Stack() 由于 Python 是一种努力尝试使用合理默认值的语言，它的split()方法在默认情况下会拆分为空白。（如果您仔细想想，这很可能也是您所期望的。）结果将是 expr 是一个值为 4、5、+、5、3、-和*的列表。
expr 列表的每个元素都将是运算符或操作数。如果我们得到一个操作数，那么我们将其嵌入到树节点中，并将其推送到栈上。另一方面，如果我们得到一个操作符，那么我们将该操作符嵌入到树节点中，并将其两个操作数弹出到节点的左、右子节点中。在这里，我们必须注意确保第一个 pop 进入正确的孩子，否则我们将在减法和除法方面遇到问题。
以下是构建树的代码：
for term in expr:
if term in "+-*/":
node = TreeNode(term)
node.right = stack.pop()
node.left = stack.pop()
else:
node = TreeNode(int(term))
stack.push(node) 注意，对于操作数，我们执行从字符串到 int 的转换。如果您想支持浮点操作数，可以使用float()。
在这个操作结束时，我们应该在栈中有一个元素，它保存完整的树。
我们现在可能希望能够计算表达式。我们构建以下小功能来帮助我们：
def calc(node):
if node.data is "+":
return calc(node.left) + calc(node.right)
elif node.data is "-":
return calc(node.left) - calc(node.right)
elif node.data is "*":
return calc(node.left) * calc(node.right)
elif node.data is "/":
return calc(node.left) / calc(node.right)
else:
return node.data 这个函数非常简单。我们传入一个节点。如果节点包含一个操作数，那么我们只返回该值。但是，如果我们得到一个操作符，那么我们就在节点的两个子节点上执行该操作符表示的操作。但是，由于一个或多个子节点也可能包含运算符或操作数，因此我们在两个子节点上递归调用calc()函数（请记住，每个节点的所有子节点也是节点）。
现在我们只需将根节点从栈中弹出，并将其传递到calc()函数中，我们就可以得到计算结果：
root = stack.pop()
result = calc(root)
print(result) 运行此程序应产生结果 18，这是(4 + 5) * (5 - 3)的结果。
前面我们提到，如果节点按顺序插入到树中，那么树的行为或多或少类似于一个列表，即每个节点只有一个子节点。我们通常希望通过填充树上的每一行来尽可能降低树的高度。这个过程称为平衡树。
有许多类型的自平衡树，如红黑树、AA 树和替罪羊树。在修改树的每个操作（如插入或删除）期间，这些操作将平衡树。
还有一些外部算法可以平衡树。这样做的好处是，您不需要在每一个操作上平衡树，而是可以在需要时保持平衡。
此时，我们将简要介绍 heap 数据结构。堆是树的特殊化，其中节点以特定方式排序。堆分为最大堆和最小堆。在最大堆中，每个父节点必须始终大于或等于其子节点。因此，根节点必须是树中的最大值。最小堆则相反。每个父节点必须小于或等于其两个子节点。因此，根节点持有最低的值。
堆用于许多不同的事情。首先，它们用于实现优先级队列。还有一种非常有效的排序算法，称为 heap sort，它使用堆。我们将在后续章节中深入研究这些问题。
在本章中，我们介绍了树结构及其一些示例用法。我们特别研究了二叉树，它是树的一个子类型，每个节点最多有两个子节点。
我们研究了如何将二叉树用作具有 BST 的可搜索数据结构。我们发现，在大多数情况下，在 BST 中查找数据比在链表中查找数据要快，尽管如果数据按顺序插入，情况并非如此，当然，除非树是平衡的。
宽度优先和深度优先搜索遍历模式也使用队列递归实现。
我们还研究了如何使用二叉树来表示算术或布尔表达式。我们建立了一个表达式树来表示算术表达式。我们展示了如何使用栈解析用 RPN 编写的表达式，构建表达式树，最后遍历它以获得算术表达式的结果。
最后，我们提到了堆，一种树结构的特殊化。我们试图至少为本章的堆奠定理论基础，这样我们就可以在即将到来的章节中实现不同目的的堆。