Swift 中具有结构的二叉树

Question

我试图在struct下面给出的帮助下制作一棵二叉树：

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

但我收到错误error: value type 'BinaryTree' cannot have a stored property that recursively contains it。这里的结构是值类型，所以我无法在其中创建相同的结构对象。

我怎样才能实现这个目标？？？

Answer 1

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

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

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
    }
}

我希望这对你有用。