Swift中用struct实现二叉树遇递归存储错误，求解决方案

你遇到的这个错误是因为Swift的struct是值类型——值类型的实例会直接把所有属性的内容嵌入自身内存中。如果你的struct里直接包含BinaryTree类型的left和right属性，就会形成无限递归：每个BinaryTree里都要装两个完整的BinaryTree，而这两个里面又要各装两个，编译器根本无法计算出这个类型的内存大小，所以报错。

下面给你两种实用的struct实现方案：

方案一：使用可选类型（最常用） #

二叉树的叶子节点本来就没有左/右子树，所以把left和right改成BinaryTree?（可选类型）就可以解决问题。可选类型对于值类型来说是一个枚举，它要么是nil（没有子树），要么包含一个BinaryTree实例，编译器可以明确计算它的内存大小。

代码示例：

struct BinaryTree {
    var value: Int
    var left: BinaryTree?  // 可选左子树
    var right: BinaryTree? // 可选右子树
}

使用示例 #

你可以这样创建节点：

// 创建叶子节点（没有子树）
let leafNode = BinaryTree(value: 5, left: nil, right: nil)
// 创建根节点，左子树是上面的叶子节点
let rootNode = BinaryTree(value: 10, left: leafNode, right: nil)

方案二：使用indirect关键字 #

Swift提供了indirect关键字，它可以让struct的递归属性变成引用语义（底层用指针存储），这样编译器就不用计算无限递归的内存大小了。你可以用它修饰整个struct，或者只修饰递归的属性：

修饰整个struct #

indirect struct BinaryTree {
    var value: Int
    var left: BinaryTree
    var right: BinaryTree
}

不过这种写法要求每个节点必须有左、右子树，不太符合常规二叉树的结构（毕竟叶子节点没有子树），所以更实用的是结合可选类型：

struct BinaryTree {
    var value: Int
    indirect var left: BinaryTree?
    indirect var right: BinaryTree?
}

这样既保留了可选子树的灵活性，又用indirect解决了递归值类型的问题。

额外补充：用Class实现（如果不需要Struct的特性） #

如果你不需要struct的值语义特性，用class实现二叉树会更直观——因为class是引用类型，天然支持递归结构：

class BinaryTree {
    var value: Int
    var left: BinaryTree?
    var right: BinaryTree?
    
    init(value: Int, left: BinaryTree? = nil, right: BinaryTree? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
}

内容的提问来源于stack exchange，提问作者Chanchal Chauhan