二叉树的定义与性质：让“树枝”变得有条理

什么是二叉树？

想象一下你正在组织一场“知识竞赛”，每个选手只能最多跟两个人比赛（比如一答一对，输了淘汰）。或者像你家的家族树，每对父母最多有两个孩子。这样的“分叉”结构在计算机里就叫二叉树。

二叉树是一种很常见的树结构，它的特点是：每个节点（就像家族里的一个人）最多只能有两个“孩子”，分别叫左孩子和右孩子。你可以没有孩子（叶子节点），也可以只有一个左孩子或只有一个右孩子，但不能超过两个。

生活中很多地方都有二叉树的身影：

文件目录：一个文件夹下最多只能有两个子文件夹（虽然现实中文件夹可以有几十个，但简化后可以用来理解二叉结构）。
体育比赛：淘汰赛中一次比赛分出两组，再往下分两组，最后决出冠军。
猜数字游戏：每次问“比50大吗？”然后分成左右两个范围。

二叉树的核心思想就是：二分，每次把问题或数据分成两半，条理清晰，查询很快。

二叉树的有趣性质（几个小规律）

二叉树就像数学里的“2的次方”一样整齐，有几条特别好用的性质：

第 i 层最多有多少个节点？
- 公式：第 i 层最多有 2^(i-1) 个节点（根节点算第 1 层）。
- 例子：第 1 层（根）最多 2^(0) = 1 个节点；第 2 层最多 2^(1) = 2 个节点；第 3 层最多 2^(2) = 4 个节点；第 4 层最多 8 个…… 是不是像细胞分裂？
深度为 h 的二叉树最多有多少个节点？
- 公式：深度为 h 的二叉树最多有 2^h - 1 个节点。
- 解释：把每一层最多的节点加起来：1 + 2 + 4 + … + 2^(h-1) = 2^h - 1。
- 例子：深度为 3 的二叉树（从上到下共 3 层），最多 2^3 - 1 = 7 个节点。如果深度是 4，最多 15 个节点。
叶子节点数 = 度为 2 的节点数 + 1（这条性质以后会用到，现在先知道就好）
- 度是指一个节点有几个孩子。度为 2 就是有左右两个孩子。
- 这条性质在计算一些题目时很有用，比如已知叶子节点个数，可以反推有 2 个孩子的节点个数。

你可能会问：“有没有刚好每个节点都有左右孩子的树？” 有的！如果一棵二叉树，每一层节点都是满的（除了最后一层可能不满），这叫满二叉树。如果最后一层从左到右连续，没有缺空，这叫完全二叉树。这些概念在以后学堆（Heap）时会用到。

用 Python 表示二叉树节点

在代码里，二叉树就像一条链条，每个节点是一个小盒子，盒子左边连着左孩子，右边连着右孩子。我们用 left 和 right 两个“指针”表示它们。如果某个孩子不存在，就用 None（空）表示。

下面是最基本的节点类，用来创建树：

class BinaryTreeNode:
    """二叉树的节点类"""
    def __init__(self, data):
        self.data = data          # 节点里存放的值（比如名字、数字）
        self.left = None          # 左孩子，初始时没有
        self.right = None         # 右孩子，初始时没有

创建节点的方法很简单：node = BinaryTreeNode("A")，然后手动把左右孩子挂上去。

# 创建一棵简单二叉树：根 A，左孩子 B，右孩子 C
root = BinaryTreeNode("A")        # 根节点A
root.left = BinaryTreeNode("B")   # 左孩子B
root.right = BinaryTreeNode("C")  # 右孩子C

# 给B加左孩子D和右孩子E
root.left.left = BinaryTreeNode("D")
root.left.right = BinaryTreeNode("E")

# 打印信息
print("根:", root.data)                    # 输出 A
print("左孩子:", root.left.data)           # 输出 B
print("右孩子:", root.right.data)          # 输出 C
print("左孩子的左孩子:", root.left.left.data)  # 输出 D
print("左孩子的右孩子:", root.left.right.data)  # 输出 E

这段代码构造了一棵这样的二叉树：

    A
   / \
  B   C
 / \
D   E

注意：C 节点还没有孩子，所以 root.right.left 是 None（空），不能直接访问它的 data，否则会报错。

新手常犯的错误

忘记左右孩子可能为空
```
# 错误写法
print(root.right.left.data)   # 如果 right 没有左孩子，直接报错
```
正确做法：先判断节点是否存在，例如 if root.right.left: print(root.right.left.data)。
混淆左孩子和右孩子的顺序
- 二叉树中左右是有意义的，比如在排序树中，左孩子比父节点小，右孩子比父节点大。如果挂反了，树的结构就错了。
认为每个节点必须有左右两个孩子
- 实际上，节点可以有 0 个、1 个（左或右）、2 个孩子。只挂一个孩子也是合法的二叉树。
忘记初始化左右孩子为 None
- 如果不写 self.left = None，那么节点创建时 left 可能是一个未定义的变量，之后赋值时容易出错。所以一定要在 __init__ 里初始化。
用列表或链表的思维访问节点
- 比如想直接 root[0] 取左孩子，那是不行的。必须用 root.left 这样的属性。

完整可运行的示例：创建一棵二叉树并统计节点个数

下面这个程序创建了一棵稍大一点的二叉树（模拟一个家族树），然后写了一个函数来计算树里一共有多少个节点，并打印所有节点值。

class BinaryTreeNode:
    """二叉树的节点类"""
    def __init__(self, data):
        self.data = data          # 节点值
        self.left = None          # 左孩子
        self.right = None         # 右孩子

def count_nodes(node):
    """统计以node为根的二叉树中节点个数"""
    if node is None:              # 如果是空节点，返回0
        return 0
    # 总数 = 左子树个数 + 右子树个数 + 1（自己）
    return 1 + count_nodes(node.left) + count_nodes(node.right)

def print_tree(node, indent=0):
    """打印二叉树（缩进显示层次）"""
    if node is None:
        return
    # 先打印右子树（让它显示在最右边）
    print_tree(node.right, indent + 4)
    print(" " * indent + str(node.data))
    # 再打印左子树
    print_tree(node.left, indent + 4)

# 创建一棵树：模拟一家人的名字
#        爷爷
#       /    \
#     爸爸    叔叔
#    /   \      \
#  哥哥  姐姐  表妹
#
root = BinaryTreeNode("爷爷")          # 根节点：爷爷
root.left = BinaryTreeNode("爸爸")     # 左孩子：爸爸
root.right = BinaryTreeNode("叔叔")    # 右孩子：叔叔
root.left.left = BinaryTreeNode("哥哥")  # 爸爸的左孩子：哥哥
root.left.right = BinaryTreeNode("姐姐") # 爸爸的右孩子：姐姐
root.right.right = BinaryTreeNode("表妹")# 叔叔的右孩子：表妹（叔叔没有左孩子）

print("=== 家族树（用缩进表示层次） ===")
print_tree(root)

print("\n总共有多少个成员？")
total = count_nodes(root)
print("节点总数:", total)               # 输出 6

运行结果：

=== 家族树（用缩进表示层次） ===
        表妹
    叔叔
爷爷
        姐姐
    爸爸
        哥哥

总共有多少个成员？
节点总数: 6

注意：打印的树是“横着”的，根在左边，右孩子在上面，左孩子在下面。这是为了方便在文本里显示。

接下来可以学什么？

树的遍历：前序、中序、后序——就像按不同顺序走访家族成员。
二叉搜索树：左小右大，查找非常快，就像在字典里找单词。
堆（Heap）：一种特殊的完全二叉树，用来实现优先队列（比如游戏中的任务优先级）。
递归算法：二叉树天生适合用递归处理（比如上面的 count_nodes 函数）。

二叉树是很多高效算法的基础，先把这个“树桩”打牢，以后的学习就会顺利多啦！