如何按内存存储结构打印Scala中的TreeSet？

核心结论 #

Scala标准库的scala.collection.immutable.TreeSet基于红黑树实现，但它对外仅暴露有序集合的接口，完全隐藏了内部树结构细节——你无法通过公共API直接获取根节点、左右分支等信息，head/firstKey返回的永远是集合中的最小元素，和内部树的根节点没有直接关联。

为什么默认拿不到根节点？ #

TreeSet的设计目标是提供高效的升序访问、插入和删除操作，红黑树的自平衡特性会自动调整结构以保证性能，因此内部树的根节点不一定是你插入的第一个元素，也不一定是集合中的最大/最小元素。而head方法是为了满足有序集合的需求，直接返回升序排列的第一个元素，和底层树的存储结构无关。

实现按内存结构打印的两种方式 #

方式一：通过反射访问内部结构（不推荐） #

利用Scala的反射机制，可以强行访问TreeSet的私有内部成员，获取红黑树的根节点并遍历打印。但这种方法严重依赖Scala的内部实现细节，不同版本的Scala可能修改底层代码，导致逻辑失效，仅适合调试场景。

示例代码：

import scala.collection.immutable.TreeSet
import scala.reflect.runtime.universe._

def printTreeSetInternal[A](tree: TreeSet[A]): Unit = {
  // 获取TreeSet内部的RedBlackTree实例
  val mirror = runtimeMirror(tree.getClass.getClassLoader)
  val treeInstanceMirror = mirror.reflect(tree)
  val redBlackTree = treeInstanceMirror.reflectField(
    tree.getClass.getDeclaredField("tree")
  ).get

  // 获取RedBlackTree的根节点
  val rbtInstanceMirror = mirror.reflect(redBlackTree)
  val rootNode = rbtInstanceMirror.reflectField(
    redBlackTree.getClass.getDeclaredField("root")
  ).get

  // 递归打印节点，处理红黑树的Node和Leaf类型
  def printNode(node: Any, indent: String = ""): Unit = {
    node.getClass.getSimpleName match {
      case "Node" =>
        // 反射获取节点值、左子树、右子树
        val value = node.getClass.getDeclaredField("value").tap(_.setAccessible(true)).get(node)
        val left = node.getClass.getDeclaredField("left").tap(_.setAccessible(true)).get(node)
        val right = node.getClass.getDeclaredField("right").tap(_.setAccessible(true)).get(node)

        println(s"$indent$value")
        if (left.getClass.getSimpleName != "Leaf") printNode(left, indent + "  / ")
        if (right.getClass.getSimpleName != "Leaf") printNode(right, indent + "  \\ ")
      case "Leaf" => // 忽略叶子节点
    }
  }

  printNode(rootNode)
}

// 测试
val tree1 = TreeSet(4, 2, 1)
println("Tree1的内部结构：")
printTreeSetInternal(tree1)

val tree2 = TreeSet(2, 1, 4)
println("\nTree2的内部结构：")
printTreeSetInternal(tree2)

方式二：自定义二叉搜索树（推荐） #

如果需要稳定可控的树结构打印，最可靠的方式是自己实现一个二叉搜索树（或红黑树），对外暴露根节点和遍历打印的方法。这样你可以完全控制树的存储结构，按照需求打印。

示例代码：

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

class CustomTreeSet[A](implicit ord: Ordering[A]) {
  private var root: Tree[A] = Leaf

  // 插入元素，维护二叉搜索树结构
  def add(value: A): Unit = {
    root = insert(root, value)
  }

  private def insert(tree: Tree[A], value: A): Tree[A] = tree match {
    case Leaf => Node(value, Leaf, Leaf)
    case Node(v, left, right) =>
      if (ord.lt(value, v)) Node(v, insert(left, value), right)
      else if (ord.gt(value, v)) Node(v, left, insert(right, value))
      else tree // 元素已存在，不重复插入
  }

  // 按树的内存结构打印（前序遍历，带缩进）
  def printTree(): Unit = {
    def printNode(node: Tree[A], indent: String = ""): Unit = node match {
      case Node(v, left, right) =>
        println(s"$indent$v")
        if (left != Leaf) printNode(left, indent + "  / ")
        if (right != Leaf) printNode(right, indent + "  \\ ")
      case Leaf => // 忽略叶子节点
    }
    printNode(root)
  }
}

// 测试
val customTree1 = new CustomTreeSet[Int]()
List(4, 2, 1).foreach(customTree1.add)
println("CustomTree1的结构：")
customTree1.printTree()
// 输出：
// 4
//   / 2
//     / 1

val customTree2 = new CustomTreeSet[Int]()
List(2, 1, 4).foreach(customTree2.add)
println("\nCustomTree2的结构：")
customTree2.printTree()
// 输出：
// 2
//   / 1
//   \ 4

内容的提问来源于stack exchange，提问作者Maor Aharon