二叉树操作与转换

题目

二叉树操作与转换

信息

• 类型：问答
• 难度：⭐⭐

考点

递归,模式匹配,不可变性,树的操作,高阶函数

快速回答

实现二叉树的三个核心操作：

• 使用递归和模式匹配计算树高度
• 通过不可变转换实现节点值增加
• 利用高阶函数转换节点为子树值列表

关键代码结构：

sealed trait Tree[+T]
case object Empty extends Tree[Nothing]
case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

原理说明

在函数式编程中处理树结构需遵循：1) 使用递归而非循环遍历；2) 通过模式匹配分解数据结构；3) 保持不可变性——每次修改返回新实例；4) 利用高阶函数抽象通用操作。

完整实现代码

sealed trait Tree[+T]
case object Empty extends Tree[Nothing]
case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

object TreeOperations {
  // 1. 计算树高度
  def height[T](tree: Tree[T]): Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + (height(left) max height(right))
  }

  // 2. 增加所有节点值
  def incrementValues(tree: Tree[Int], delta: Int): Tree[Int] = tree match {
    case Empty => Empty
    case Node(v, l, r) => Node(v + delta, incrementValues(l, delta), incrementValues(r, delta))
  }

  // 3. 转换节点为子树值列表
  def toSubtreeLists[T](tree: Tree[T]): Tree[List[T]] = {
    def collectValues(t: Tree[T]): List[T] = t match {
      case Empty => Nil
      case Node(v, l, r) => v :: (collectValues(l) ::: collectValues(r))
    }

    tree match {
      case Empty => Empty
      case n @ Node(_, l, r) => 
        Node(collectValues(n), toSubtreeLists(l), toSubtreeLists(r))
    }
  }
}

最佳实践

• 尾递归优化：对于深度大的树，可将height改为尾递归（需添加accumulator参数）
• 记忆化：toSubtreeLists中collectValues存在重复计算，可缓存子树结果
• 类型安全：使用sealed trait确保模式匹配覆盖所有分支

常见错误

• 忘记空节点处理：缺失Empty分支会导致MatchError
• 副作用操作：尝试直接修改节点值（如case Node(v, l, r) => v += delta）违反不可变性
• 低效列表拼接：在collectValues中使用:::拼接大列表效率低，应改用ListBuffer

扩展知识

• Catamorphisms：可用fold函数统一树操作（如def fold[T,U](z: U)(f: (T, U, U) => U): U）
• 类型类：通过Functor实现map操作（如def map[U](f: T => U): Tree[U]）
• 并行化：递归操作可结合Future实现并行子树处理