一、一棵树长什么样

演示里那棵树：最上面是 8，下面分 4 和 12，4 下面再分 2 和 6，12 下面分 10 和 14。 术语三个就够：最上面那个叫根，往下分出来的叫子节点，没有孩子的叫叶子。 树和前面那些结构最大的不同：它的数据有上下级关系。一行数组里没有谁管谁，树里有。

所以只要你的数据本身是「一层一层的」——文件夹、部门、分类目录、家族——它就天然是树， 硬塞进数组反而要另外记「谁是谁的上级」。 一个节点最多有两个孩子，就叫二叉树。 演示里那棵每个节点都正好两个，叫满二叉树（这个说法教材没强调，知道就行）。

二、三种走法，差别只在什么时候记下自己

把树上的值全列出来，有三种走法。三种的结果完全不同，但每种都只列一遍。

记法很简单：想象自己站在节点上， 前序是先写下自己再往下走，中序是先走左边再写自己，后序是两个孩子都走完才写自己。 三种走法都是递归——走完左边走右边，走法一样。第 7 章讲递归时会回到这里。 为什么要有三种？ 因为用途不同：复制一棵树用前序，排序用中序，释放内存用后序（得先把孩子删了才能删自己）。

三、中序为什么值得单独说

演示里那句发现最值钱：中序结果 2 4 6 8 10 12 14 正好是从小到大。 不是碰巧。 这棵树的摆法有条规矩：左边都比自己小，右边都比自己大。8 左边是 4 和 2、6，全比 8 小； 右边 12、10、14 全比 8 大。 这种树叫二叉搜索树（教材没给这个名字，但它就是后面搜索用的那棵树）。

在它上面，中序走一遍就等于排序——不用比较，直接读出来就是有序的。 反过来说：随便摆一棵树，中序不一定有序。有序是摆法带来的，不是树带来的。这个区别很多人会混。

四、找 6，比几次

从根 8 出发找 6：6 比 8 小，往左到 4；6 比 4 大，往右到 6。三次。 一个一个找的话，七个数最坏要比七次。这里三次就中了。 为什么快？因为每比一次就扔掉一半：比 8 小，右边那半整棵不用看了。这正是第 6 章二分搜索的做法。

数据一多，这个差距拉开得极快。 100 万个数据，这样的树最多比 20 次（因为 2 的 20 次方已经超过 100 万），线性找最坏要 100 万次。 演示里那句「指数级」说的是这个：数据翻倍，树只多比一次，线性找要多比一倍。

五、动手 Demo：建一棵二叉树，三种走法走一遍

先照演示里那棵树的样子建出来：8 是根，左右各两个孩子。 再用前序、中序、后序各走一遍，对比三个结果。 最后从根出发找 6，数一数比了几次。

class Node:
    def __init__(self, v):
        self.v, self.l, self.r = v, None, None

def build(a, lo, hi):
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    n = Node(a[mid])
    n.l = build(a, lo, mid - 1)
    n.r = build(a, mid + 1, hi)
    return n

root = build([2, 4, 6, 8, 10, 12, 14], 0, 6)

def order(n, how):
    if not n:
        return []
    if how == 'pre':
        return [n.v] + order(n.l, how) + order(n.r, how)
    if how == 'in':
        return order(n.l, how) + [n.v] + order(n.r, how)
    return order(n.l, how) + order(n.r, how) + [n.v]

for h in ('pre', 'in', 'post'):
    print(h, order(root, h))

n, cnt = root, 0
while n:
    cnt += 1
    if n.v == 6:
        break
    n = n.l if 6 < n.v else n.r
print('找 6 比了', cnt, '次')

实跑输出：

--------------------------------------------------------------------
树与二叉树：有层级的数据
--------------------------------------------------------------------


  ① 一棵树长什么样
  --------------------------------------------------------------------
        8
      /   \
     4     12
    / \   /  \
   2   6 10   14
  最上面那个叫根，往下分叉的叫子节点，没有孩子的叫叶子。
  教材的比方是树干、树枝、树叶——一层管下一层。
  一个节点最多两个孩子，就叫二叉树。上图的每个节点都正好两个。

  ② 三种走法，三种顺序
  --------------------------------------------------------------------

| 走法 | 访问顺序 |
|---|---|
| 前序 | 8 4 2 6 12 10 14 |
| 中序 | 2 4 6 8 10 12 14 |
| 后序 | 2 6 4 10 14 12 8 |

  三种走法的区别只在「什么时候记下自己」：进门前记是前序，两孩子中间记是中序，出来再记是后序。

  ③ 中序为什么值得单独说
  --------------------------------------------------------------------
  中序结果是 2 4 6 8 10 12 14 —— 正好从小到大
  因为这棵树的摆法有个规矩：左边都比自己小，右边都比自己大。
  这种树叫二叉搜索树，中序走一遍就等于排序。

  ④ 找 6，比几次
  --------------------------------------------------------------------
  从根开始：8 -> 4 -> 6，比了 3 次
  如果一个一个找：要 7 次
  7 个数据，二叉树 3 次就找到，线性找要 7 次。
  数据一多，差距是指数级的——100 万个数据，二叉树最多 20 次，线性找最坏 100 万次。
  这就是第 6 章二分搜索的同一个道理，只是这里用树来组织。

①build 是拿一个有序数组对半切出来的，所以建出来天然满足「左小右大」。 手写的话要一个个插，麻烦得多。 ②order 一个函数出三种结果，差别只在 [n.v] 放在三个位置的哪一个。 前序放最前，中序放中间，后序放最后。 ③中序结果是 2 4 6 8 10 12 14，和输入的数组一模一样——因为它们本来就是有序的， 而对半切出来的正好是二叉搜索树。 ④找 6 那个循环 n = n.l if 6 < n.v else n.r 就是「小往左、大往右」，比了 3 次。

30 秒实验

1. 把 build 换成「每个节点只挂右孩子」（一条链），再看找 14 要几次。
2. 往这棵树里找 5（不存在），看它比几次、最后停在哪。
3. 把三种走法的顺序改成「先右后左」，看结果变成什么样。

常见误区

1. 「树的中序遍历一定有序。」只有二叉搜索树才有序。随便摆的树，中序只是中序。
2. 「树就是链表加了分叉。」链表每个节点一个后继，树有两个（二叉树），还多了上下级关系。
3. 「树找数快，所以什么数据都该建成树。 」建成树要额外维护「左小右大」，数据天天变的话维护成本很高。

树有个限制：不能有圈。 要是允许几个节点互相连着，就成了网状——地图、社交关系、地铁线路都是这种东西。 下一节讲图，顺带把「下标从 0 还是 1」这笔老账算清。

• ☐ （本篇完，下一篇 3.6 图，以及下标从 0 还是 1）

相关笔记

• 数组、链表与环形缓冲区
• 图，以及下标从 0 还是 1
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引