Python 二叉树
树是一种由边连接的节点组成的层次数据结构。
每个节点包含一个值和对其子节点的引用。
二叉树
二叉树是一种树数据结构，其中每个节点最多可以有两个子节点，即左子节点和右子节点。
这种限制，即一个节点最多可以有两个子节点，为我们带来了许多好处：
- 遍历、搜索、插入和删除等算法更容易理解、实现和运行得更快。
- 在二叉搜索树（BST）中保持数据有序可以使搜索非常高效。
- 使用 AVL 二叉树等例子，可以更容易地平衡具有有限数量子节点的树。
- 二叉树可以表示为数组，使树更加内存高效。
二叉树实现
上面的二叉树可以像链表一样实现，只是我们不是将每个节点链接到一个下一个节点，而是创建一个结构，其中每个节点可以链接到其左子节点和右子节点。
实例
在 Python 中创建二叉树：
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# 测试
print("root.right.left.data:", root.right.left.data)
二叉树的类型
二叉树有不同的变体或类型，讨论这些有助于更好地理解二叉树的结构。
现在也值得一提的是不同类型的二叉树，因为这些词汇和概念将在本教程的后面部分使用。
以下是不同类型二叉树结构的简短解释，以及这些结构的示意图，以便尽可能容易理解。
平衡二叉树：对于树中的每个节点，其左子树和右子树的高度差最多为 1。
完全二叉树：除了最后一层可能不满外，其他所有层都满，且最后一层从左到右填充。完全二叉树的性质意味着它也是平衡的。
满二叉树：每个节点要么有0个子节点，要么有 2 个子节点。
完美二叉树：所有叶子节点都在同一层，这意味着所有层都满，且所有内部节点都有两个子节点。完美二叉树的性质意味着它也是满的、平衡的和完全的。
二叉树遍历
遍历树意味着逐个访问每个节点。
由于数组和链表是线性数据结构，因此只有一种明显的遍历方式：从第一个元素或节点开始，继续访问下一个，直到访问完所有元素或节点。
但由于树可以向不同方向分支（非线性），因此有几种不同的遍历树的方式。
树遍历方法主要有两大类：
广度优先搜索（BFS）：在访问下一层的节点之前，先访问同一层的所有节点。这意味着树的探索方向更偏向于横向。
深度优先搜索（DFS）：遍历一直向下到叶子节点，以向下的方向逐个分支探索树。
DFS 有三种不同的类型：
- 前序遍历
- 中序遍历
- 后序遍历
二叉树的前序遍历
前序遍历是深度优先搜索的一种类型，其中每个节点都按照一定的顺序被访问。
前序遍历是通过首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历来完成的。它用于创建树的副本、表达式树的前缀表示等。
这种遍历被称为“前序”，是因为节点在递归前序遍历左子树和右子树之前被访问。
以下是前序遍历的代码示例：
实例
前序遍历：
def preOrderTraversal(node):
if node is None:
return
print(node.data, end=", ")
preOrderTraversal(node.left)
preOrderTraversal(node.right)
第一个被打印的节点是节点 R，因为前序遍历的工作方式是首先访问或打印当前节点（第 4 行），然后再递归地调用左子节点和右子节点（第 5 行和第 6 行）。
preOrderTraversal() 函数会一直递归地遍历左子树（第 5 行），然后再去遍历右子树（第 6 行）。因此，接下来被打印的节点是 'A'，然后是 'C'。
第一次当参数 node 为 None 时，是当节点C的左子节点作为参数给出时（C 没有左子节点）。
在第一次调用 C 的左子节点返回 None 后，C 的右子节点也返回 None，然后递归调用继续回溯，以便接下来打印 A 的右子节点 D。
代码继续回溯，以便打印 R 的右子树中的其余节点。
二叉树的中序遍历
中序遍历是深度优先搜索的一种类型，其中每个节点都按照一定的顺序被访问。
中序遍历首先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。这种遍历主要用于二叉搜索树，其中它按升序返回值。
这种遍历之所以被称为“中序”，是因为节点在递归函数调用之间被访问。节点在左子树的中序遍历之后被访问，在右子树的中序遍历之前被访问。
以下是中序遍历的代码示例：
实例
创建中序遍历：
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
inOrderTraversal() 函数会一直以当前左子节点作为参数调用自身（第 4 行），直到该参数为 None 且函数返回（第 2-3 行）。
第一次当参数 node 为 None 时，是当节点 C 的左子节点作为参数给出时（C 没有左子节点）。
之后，打印节点 C 的 data 部分（第 5 行），这意味着 'C' 是第一个被打印的内容。
然后，将节点 C 的右子节点作为参数给出（第 6 行），该节点为 None，因此函数调用返回而不执行其他任何操作。
在 'C' 被打印后，之前的 inOrderTraversal() 函数调用继续运行，以便 'A' 被打印，然后是 'D'，接着是 'R'，依此类推。
二叉树的后序遍历
后序遍历是深度优先搜索的一种类型，其中每个节点都按照一定的顺序被访问。
后序遍历首先递归地对左子树和右子树进行后序遍历，然后访问根节点。它用于删除树、表达式树的后缀表示等。
这种遍历之所以被称为“后序”，是因为在递归调用左子节点和右子节点之后才访问节点。
以下是后序遍历的代码示例：
实例
Post-order Traversal:
def postOrderTraversal(node):
if node is None:
return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print(node.data, end=", ")
postOrderTraversal() 函数会一直递归地遍历左子树（第 4 行），直到当 C 的左子节点作为 node 参数调用时返回 None。
在 C 的左子节点返回 None 后，第 5 行运行，C 的右子节点也返回 None，然后打印字母 'C'（第 6 行）。
这意味着 C 是在其左子节点和右子节点被遍历之后被访问或打印的，这就是为什么它被称为“后序”遍历。
postOrderTraversal() 函数继续回溯到之前的递归函数调用，因此下一个被打印的节点是 'D'，然后是 'A'。
函数继续回溯并打印节点，直到所有节点都被打印或访问。