实验课2 二叉树及其遍历 R代码整理¶

对应材料：

实验/实验课件/实验课2-二叉树及其遍历.pptx
回放/生物信息学（协和班）第5周星期4第8,9节_笔记.txt
老师板书整理

本节考试要求¶

1. 本节要求¶

这节实验课属于 R 语言高级编程。
内容主线是：
理解二叉树结构
理解先序 / 中序 / 后序遍历
会用 list 表示节点
会写递归函数完成：
- 创建节点
- 插入节点
- 搜索节点
- 找最小节点
- 删除节点
- 遍历输出

2. 考试掌握程度¶

老师明确说：这节课比实验课 1 难，属于“中等偏下到中等”的算法题，不是最基础的编程。
但老师也明确说：期末不会考得这么完整、这么难。
真正要求是：
要理解二叉树的逻辑
要理解递归
要能看懂伪代码并能写出核心函数思路

3. 老师重点强调¶

这节课最核心的关键词就是：递归。
板书里老师重点写了两个函数：
insertNode()
searchNode()
老师反复强调：
前面几个函数如果理解递归，其实代码并不多
最难的是 deleteNode() 里“用右子树最小值替换当前节点，再删掉那个最小值”这两步逻辑
遍历部分里，老师说：
先序 / 中序 / 后序都要理解
但这节实验课实际要求输出的是中序遍历结果

4. 与期末重点重合¶

高度重合，优先复习：这节课属于老师最后两节课里明确点名的“稍复杂一点的编程题 / 高级编程思想”。
与期末重点中的“基础编程 + 稍复杂编程 + 实验课代码思路”直接重合。
虽然老师说不一定完整考一棵树的所有函数，但：
递归
查找
插入
中序遍历 这些都很值得重点复习。

一、结合板书、课件和回放整理后的主干 R 代码¶

# 1. 创建节点
createNode <- function(value) {
  list(
    value = value,
    left = NULL,
    right = NULL
  )
}

# 2. 插入节点
insertNode <- function(node, value) {
  if (is.null(node)) {
    return(createNode(value))
  }

  if (value <= node$value) {
    node$left <- insertNode(node$left, value)
  } else {
    node$right <- insertNode(node$right, value)
  }

  return(node)
}

# 3. 搜索节点
searchNode <- function(node, value) {
  if (is.null(node) || node$value == value) {
    return(node)
  }

  if (value < node$value) {
    return(searchNode(node$left, value))
  } else {
    return(searchNode(node$right, value))
  }
}

# 4. 找最小值节点
findMinNode <- function(node) {
  current <- node

  while (!is.null(current$left)) {
    current <- current$left
  }

  return(current)
}

# 5. 删除节点
deleteNode <- function(node, value) {
  if (is.null(node)) {
    return(NULL)
  }

  if (value < node$value) {
    node$left <- deleteNode(node$left, value)
  } else if (value > node$value) {
    node$right <- deleteNode(node$right, value)
  } else {
    if (is.null(node$left)) {
      return(node$right)
    } else if (is.null(node$right)) {
      return(node$left)
    } else {
      minNode <- findMinNode(node$right)
      node$value <- minNode$value
      node$right <- deleteNode(node$right, minNode$value)
    }
  }

  return(node)
}

# 6. 中序遍历：左 -> 根 -> 右
inorderTraversal <- function(node) {
  if (is.null(node)) {
    return(NULL)
  }

  c(
    inorderTraversal(node$left),
    node$value,
    inorderTraversal(node$right)
  )
}

# 7. 先序遍历：根 -> 左 -> 右
preorderTraversal <- function(node) {
  if (is.null(node)) {
    return(NULL)
  }

  c(
    node$value,
    preorderTraversal(node$left),
    preorderTraversal(node$right)
  )
}

# 8. 后序遍历：左 -> 右 -> 根
postorderTraversal <- function(node) {
  if (is.null(node)) {
    return(NULL)
  }

  c(
    postorderTraversal(node$left),
    postorderTraversal(node$right),
    node$value
  )
}

# 9. 主程序：创建一棵树
root <- createNode(50)

for (v in c(30, 20, 40, 70, 60, 80)) {
  root <- insertNode(root, v)
}

# 原始中序遍历
inorderTraversal(root)

# 删除 20 后的中序遍历
root <- deleteNode(root, 20)
inorderTraversal(root)

# 删除 30 后的中序遍历
root <- deleteNode(root, 30)
inorderTraversal(root)

# 删除 50 后的中序遍历
root <- deleteNode(root, 50)
inorderTraversal(root)

# 搜索示例
searchNode(root, 60)

二、板书里最核心的两个函数¶

老师板书最重点写的是这两个：

1. `insertNode()`¶

板书逻辑就是：

insertNode <- function(node, value) {
  if (is.null(node)) {
    return(createNode(value))
  }

  if (value <= node$value) {
    node$left <- insertNode(node$left, value)
  } else {
    node$right <- insertNode(node$right, value)
  }

  return(node)
}

这段代码最重要的点有两个：

如果当前节点为空，就在这里新建节点
如果不为空，就根据大小决定往左子树还是右子树继续插

这就是典型递归：

你只写了一次 insertNode
但它会不断调用自己，直到找到空位置

2. `searchNode()`¶

板书逻辑就是：

searchNode <- function(node, value) {
  if (is.null(node) || node$value == value) {
    return(node)
  }

  if (value < node$value) {
    return(searchNode(node$left, value))
  } else {
    return(searchNode(node$right, value))
  }
}

这段代码的核心是：

空节点：返回空
找到了：直接返回当前节点
目标值更小：去左边找
目标值更大：去右边找

三、这节课每一部分在考什么¶

1. 二叉树结构¶

每个节点最多两个子树：左子树、右子树
课件和回放里都在强调：
二叉树可以是空的
也可以只有根节点
也可以只有左子树或右子树

2. 遍历的三个核心顺序¶

课件写的是：

DLR：先序遍历
LDR：中序遍历
LRD：后序遍历

老师回放里反复强调：

它们的区别，关键看“根节点在什么时候被访问”
根节点第一次访问：先序
根节点中间访问：中序
根节点最后访问：后序

3. 二叉搜索树的大小关系¶

这节课默认是在讲二叉搜索树，核心规律是：

左子树的值 < 根节点的值 < 右子树的值

老师在回放里几乎一直围绕这个规律在讲：

插入为什么走左/右
查找为什么走左/右
删除为什么要找右子树最小值

4. 递归¶

这是本节最核心的概念。

老师反复强调：

不理解递归，这些函数会觉得很复杂
理解递归之后，代码其实很短

你可以把递归理解成：

当前问题如果解决不了
就把同样的问题交给“更小的一棵子树”
直到碰到边界条件（比如 NULL）为止

四、删除节点为什么最难¶

老师明确说，难点主要就在 deleteNode() 最后那两步。

删除节点分三种情况：

1. 这个节点没有左子树¶

直接返回右子树

2. 这个节点没有右子树¶

直接返回左子树

3. 这个节点左右子树都有¶

这是最难的情况：

去右子树里找最小值节点
用这个最小值替换当前节点值
再到右子树中把这个最小值原来那个节点删掉

比如课件主程序里删 50：

找到 50
它左右子树都存在
去右子树找最小值，得到 60
用 60 替换 50
再把原来的 60 节点删掉

这就是老师回放里说的“最难的是后面那两行逻辑”。

五、老师实际要求你做到什么程度¶

1. 不要求你把整套代码都默写得非常长¶

老师明确说：期末不会考这么完整、这么难。
但“不会完整照抄考”不等于“可以不看”。

2. 要理解伪代码¶

老师在回放里说得很明确：

要学会看课件上的“伪代码”
因为伪代码基本上就是代码思路本身

也就是说，你至少要做到：

看懂课件上的 IF / ELSE / RETURN
能翻成 R 代码

3. 真正最该掌握的是这些点¶

节点怎么表示
为什么节点用 list
递归的边界条件是什么
插入为什么左小右大
搜索为什么可以只走一条路径
中序遍历为什么能输出有序结果
删除双子节点时为什么找“右子树最小值”

4. 这节课更像“大编程思路训练”¶

老师把它定义成：

不是最基础的编程
也不是特别高难度
是一种典型的中等算法题

而且老师还举了应用化变形的例子：

不一定考“数值”
也可能换成“学生成绩”“某个值的搜索”
本质还是同一个二叉搜索树逻辑

六、最适合考试背的最短主线¶

创建节点
-> 依次插入节点构造二叉搜索树
-> 按大小关系递归搜索节点
-> 找右子树最小值辅助删除
-> 删除节点
-> 用中序遍历输出结果

七、这节课最容易被问的点¶

什么是二叉树
什么是二叉搜索树
先序 / 中序 / 后序分别是什么
为什么中序遍历能得到从小到大的结果
递归的结束条件是什么
insertNode() 为什么最后要 return(node)
searchNode() 为什么只走左边或右边，不需要两边都找
删除有两个子节点的节点时，为什么要找右子树最小值

八、如果考试让你用文字描述，可以这样写¶

先定义节点结构，每个节点包含 value、left、right 三部分。然后利用插入函数递归构建二叉搜索树，满足左子树值小于根节点值、右子树值大于根节点值。查找节点时，根据目标值与当前节点值的大小关系递归进入左子树或右子树。删除节点时，若目标节点只有一个子树，则直接返回该子树；若左右子树都存在，则用右子树中的最小值节点替换当前节点，再递归删除右子树中的该最小值节点。遍历时可用递归实现先序、中序和后序，其中中序遍历顺序为左子树、根节点、右子树。

九、一句总结¶

这节实验课表面上是在写二叉树，实际上老师最想让你学会的是：如何把一个稍复杂的算法结构拆成多个递归函数来写。真正的核心不是背树，而是理解递归、理解左小右大、理解删除节点时的替换逻辑。