结构在 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

你可以对这个结构使用class，结构不允许引用自身。

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

let node = BinaryTree.init(value: 1)
node.left = BinaryTree(value: 2)

The reason for this compile error is memory allocation: Value types are fixed structures and they occupy a fixed space in memory, in registers and the stack, depending on its size. That space is pre-determined by the type and must be known at compile time.

https://medium.com/@leandromperez/bidirectional-associations-using-value-types-in-swift-548840734047

Answer 2

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

的解决方案

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

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，结构不允许引用自身。

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

我希望这对你有用。

Answer 3

要使用值类型构造树，您需要将协议添加到组合中。这是一个例子：

protocol Node {
  var value: Int {get}
}

struct Tree: Node {
  var value: Int
  var  left: Node
  var right: Node
}

struct Leaf: Node {
  var value: Int
}

结构在 swift 中的二叉树

Binary Tree with struct in swift

tree

binary-tree

data-structures

swift