小探险家学算法

Appearance

19. 家族树（二叉树） ​

知识点：二叉树 —— 每个节点最多两个"孩子"；遍历：前序/中序/后序/层序

项目：画一张"家谱树" + 电脑文件夹树

故事开场：家谱怎么存？ ​

老师布置了一个作业："用程序表示你的家谱：爷爷、爸爸、叔叔、我、 妹妹、堂哥……还要能查'谁是谁的孩子'。"

你试了试数组：

ts
const family = ["爷爷", "爸爸", "叔叔", "我", "妹妹", "堂哥"]

"谁是爸爸的孩子？"你盯着数组，"这……看不出来啊！全挤在一排， 关系全丢了！"

你又想起第 9 章的链表：火车车厢一节钩一节，可那是一个钩子连一个—— 爸爸有两个孩子（我和妹妹），一个钩子不够用啊！

笨办法先行：怎么"分叉"？ ​

链表解决不了，因为链表是一条线。家谱是分叉的：

          爷爷
        ↙      ↘
      爸爸      叔叔
     ↙    ↘       ↘
    我    妹妹      堂哥

爷爷往下分叉成两个孩子（爸爸、叔叔）；爸爸又分叉成两个孩子 （我、妹妹）；叔叔分叉成堂哥。

"爸爸"能连着"我"和"妹妹"两个——所以每个"人"需要两个钩子！

回想一下链表的节点：{ name, next }（一个值 + 一个钩子）。 那家谱的节点应该是：{ name, 左孩子, 右孩子 }——一个值 + 两个钩子！

引出知识点：二叉树——一爹两娃 ​

树（tree）：像家谱这样，从"根"开始不断分叉的结构。 二叉树（binary tree）：每个节点最多两个孩子（左孩子、右孩子） 的树。binary 就是"二"——最多分两个叉。

树的术语（都很形象，记名字就行）：

术语意思家谱里的例子
根节点最顶上的节点，整棵树的起点爷爷
父节点 / 子节点上下连着的一对爸爸是爷爷的孩子，也是我的爸爸
叶节点没有孩子的节点我、妹妹、堂哥
左孩子 / 右孩子左边的分叉 / 右边的分叉爸爸的左孩子是我

树和链表的血缘关系：链表是一棵"只有右孩子、没有左孩子"的树！ 一个钩子（next）变成两个钩子（left + right），一条线就长成了一棵树。

在 TypeScript 里，二叉树的节点长这样：

ts
type TreeNode = {
  value: string
  left: TreeNode | null     // 左孩子（钩子）
  right: TreeNode | null    // 右孩子（钩子）
}

function makeNode(value: string): TreeNode {
  return { value: value, left: null, right: null }
}

动手实现：种一棵家谱树 ​

把家谱"种"出来——和组装火车很像，只是多了个右钩子：

ts
const root = makeNode("爷爷")    // 根节点

const dad = makeNode("爸爸")
const uncle = makeNode("叔叔")
root.left = dad                  // 爷爷的左孩子：爸爸
root.right = uncle               // 爷爷的右孩子：叔叔

const me = makeNode("我")
const sister = makeNode("妹妹")
dad.left = me
dad.right = sister

const cousin = makeNode("堂哥")
uncle.left = cousin

树种好了。现在，遍历——把树上的人一个个"走"一遍。

最简单的走法，和递归打印文件夹一样（第 15 章！）：先走自己， 再走左孩子，再走右孩子。这叫前序遍历（先走"前"面的自己）：

ts
// 前序遍历：自己 → 左孩子 → 右孩子
function preorder(node: TreeNode | null): void {
  if (node === null) {
    return                      // 走到头了（空钩子），回来
  }
  console.log(node.value)       // 先看自己
  preorder(node.left)           // 再走左子树
  preorder(node.right)          // 最后走右子树
}

preorder(root)

输出：

爷爷
爸爸
我
妹妹
叔叔
堂哥

就这几行！ 递归像一把万能钥匙：不管树有多深、有多少节点， "先自己、再左边、再右边"一直套娃，整棵树就被走遍了。

跑起来：四种遍历 ​

同一个"自己、左、右"的顺序，稍微换一换位置，就变成三种遍历：

ts
// 前序：自己 → 左 → 右（我们刚写的）
// 中序：左 → 自己 → 右
function inorder(node: TreeNode | null): void {
  if (node === null) { return }
  inorder(node.left)
  console.log(node.value)
  inorder(node.right)
}

// 后序：左 → 右 → 自己
function postorder(node: TreeNode | null): void {
  if (node === null) { return }
  postorder(node.left)
  postorder(node.right)
  console.log(node.value)
}

console.log("前序：")
preorder(root)
console.log("中序：")
inorder(root)
console.log("后序：")
postorder(root)

输出：

前序：
爷爷 爸爸 我 妹妹 叔叔 堂哥
中序：
我 爸爸 妹妹 爷爷 堂哥 叔叔
后序：
我 妹妹 爸爸 堂哥 叔叔 爷爷

三种顺序，名字都起得很形象："自己"什么时候被打印，就叫什么序 （前 = 先打印自己；中 = 中间打印自己；后 = 最后打印自己）。

还有一种"从上到下、一层一层"的走法，叫层序遍历——用第 7 章的 队列！（第一层进队列，处理完把孩子们排到队尾……）

ts
// 层序遍历：一层一层走（用队列！）
function levelOrder(root: TreeNode): void {
  const queue: TreeNode[] = []
  queue.push(root)                    // 根节点先排队

  while (queue.length > 0) {
    const node = queue.shift()        // 队首出队
    if (node === undefined) { break }
    console.log(node.value)
    if (node.left !== null) { queue.push(node.left) }    // 孩子排到队尾
    if (node.right !== null) { queue.push(node.right) }
  }
}

console.log("层序：")
levelOrder(root)

输出：

层序：
爷爷 爸爸 叔叔 我 妹妹 堂哥

看，"一层一层"正好是"先进先出"——第一层先到（先出队）， 第二层的孩子排后面。队列和树，天生一对！

小挑战 ​

  1. 文件夹树：电脑里的文件夹就是一棵树（文件夹里有子文件夹）。 用树存一个文件夹结构，递归打印成"缩进树"（提示：遍历时记录 深度，打印几个空格再打印名字——第 15 章挑战过类似题）。
  2. 数一数：写一个函数数出树上一共有多少个节点（提示： 递归：1 + 左子树的节点数 + 右子树的节点数）。
  3. 树有多高：写一个函数算出树有多高（从根到最深的叶子 要走几步）（提示：1 + max(左子树高度, 右子树高度)—— Math.max 可以比大小）。
  4. 找叶子：输出所有"没有孩子"的节点（提示：左钩子和右钩子 都是空，就是叶子）。

课后练习 ​

第 1 题（动手题）：种一棵成绩树 ​

用 makeNode 种一棵"成绩树"：

      80
    ↙    ↘
   60     90
  ↙  ↘      ↘
 50   70     95

然后用四种遍历分别打印它，对照答案检查顺序。

参考答案（点开查看）
ts
const r = makeNode("80")
const a = makeNode("60")
const b = makeNode("90")
const c = makeNode("50")
const d = makeNode("70")
const e = makeNode("95")
r.left = a
r.right = b
a.left = c
a.right = d
b.right = e

四种遍历输出：

  • 前序（自己→左→右）：80 60 50 70 90 95
  • 中序（左→自己→右）：50 60 70 80 90 95
  • 后序（左→右→自己）：50 70 60 95 90 80
  • 层序（一层一层）：80 60 90 50 70 95

咦，中序输出刚好是从小到大排好序的！ 这不是巧合——下一章 《会找路的树》的秘密就藏在这里：如果树里"左边的都小、右边的都大"， 中序遍历就是排序！

第 2 题（思考题）：链表是树吗？ ​

我们说"链表是一棵只有右孩子、没有左孩子的树"。那么反过来—— 树是链表吗？ 树能不能用"一个钩子"的链表存？

参考答案（点开查看）

不能。链表的一个节点只有一个钩子（next），只能连一个下一个节点； 树的节点有两个钩子（left + right），能连两个。

一个钩子只能串成一条线，两个钩子才能长成一棵树。 所以链表是"退化的树"（只有一条路），树是"升级的链表"（能分叉）。

想想看：如果硬要用链表存家谱，要么丢关系，要么用别的花招 （比如"孩子链表"：每个节点再挂一个装着所有孩子的链表）—— 但那就不是"一棵树"了，是树和链表的组合。

第 3 题（思考题）：递归为什么适合树？ ​

遍历树用递归特别自然（"先自己，再左，再右"）。用循环写前序遍历， 你会遇到什么麻烦？（提示：走完左子树，怎么"回到"父节点再走右子树？ 递归靠什么记住"走到哪了"？）

参考答案（点开查看）

麻烦在于"回来"：循环往下走容易，可走完左子树要回到父节点 再走右子树——循环没有"记忆"，不知道回去的路。

递归靠调用栈（第 6 章！）自动记住：每递归一层，系统就 把"走到哪了"记在栈上，返回时自动弹出。所以递归写树遍历 只需要 3 行；循环版要自己维护一个栈（或者队列）——也能写， 但要写的代码多得多。

递归 = 让系统帮你记账。 树的形状天生适合递归：树的定义 （"节点 + 左子树 + 右子树"）本身就是递归的！

下一课预告：期中考试出成绩了。老师要一个"成绩管理器"： 随时可以查询"有没有 88 分"、插入新成绩、按顺序打印。 数组？插入要挪位。Map？查得快但没法按顺序打印。 有没有一种树，左边的都比自己小、右边的都比自己大——查起来 像二分查找，插起来像链表？