swift - swift 结构二叉树

Question

我试图在 struct 的帮助下制作一个二叉树，如下所示:

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

但我收到错误错误:值类型“BinaryTree”不能具有递归包含它的存储属性。 这里的结构是值类型，所以我不能在其中创建相同的结构对象。

我怎样才能做到这一点？？？

Answer 1

Structs 是值类型，这就是递归不起作用的原因。您必须改用 Class，因为它们是引用类型。 但是正如您所说，您想要一个具有值类型的解决方案。这是使用 enum

的解决方案

具有间接 情况的枚举分配在堆上，因此仅包含指向递归子项的指针。 如果没有指针间接，类型将无限大，因为它包含无限多次。

enum BinaryTree<Element: Comparable> {
    case empty
    indirect case node(value: Element, left: BinaryTree<Element>, right: BinaryTree<Element>)
}

extension BinaryTree {
    func addNode(_ newValue: Element) -> BinaryTree<Element> {
        switch self {
        case .empty:
            return BinaryTree.node(value: newValue, left: .empty, right: .empty)
        case let .node(value, left, right):
            if newValue < value {
                return BinaryTree.node(value: value, left: left.addNode(newValue), right: right)
            } else {
                return BinaryTree.node(value: value, left: left, right: right.addNode(newValue))
            }
        }    
    } 
}

let tree = BinaryTree<Int>.empty.addNode(2)

或

你只需使用 Class

您可以为该结构使用类，结构不允许引用自身。

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

我希望这对你有用。