swift - 使用 Swift 枚举的二叉树实现

Question

我正在对 Swift 枚举进行一些实验以更加熟悉它们，并实现了一个基本的二叉树。它在最多添加三个项目时有效，但添加更多项目不会改变它，我不明白为什么它不起作用。

代码如下:

protocol TreeProtocol {
    mutating func insert(value: Int)
    func walk()
}


enum Tree:TreeProtocol {
    case Empty
    case Leaf(Int)
    case Node(Int, TreeProtocol?, TreeProtocol?)

    init(){
        self = .Empty;
    }

    init(value: Int) {
        self = .Leaf(value)
    }

    init(value: Int, left:TreeProtocol?, right:TreeProtocol?){
        self = .Node(value, left, right);
    }

    mutating func insert(value: Int) {
        switch self {
        case .Empty:
            self = .Leaf(value)

        case .Leaf(let currentNodeValue):
            let newTree = Tree(value: value) // var here generates a warning
            if value < currentNodeValue {
                self = .Node(currentNodeValue, newTree, .None)
            }
            else {
                self = .Node(currentNodeValue, .None, newTree)
            }

        case let .Node(currentNodeValue, leftNode, rightNode):
            if (value < currentNodeValue) {
                if leftNode == nil {
                    let newTree = Tree(value: value)
                    self = .Node(currentNodeValue, newTree, rightNode)
                }
                else {
                    var l = leftNode! // unable to call leftNode!.insert() directly
                    l.insert(value)
                }
            }
            else {
                if rightNode == nil {
                    let newTree = Tree(value: value)
                    self = .Node(currentNodeValue, leftNode, newTree)
                }
                else {
                    var r = rightNode!
                    r.insert(value)
                }
            }
        }
    }

    func walk() {
        switch self {
        case .Empty:
            print("Empty")
        case .Leaf (let value):
            print("\(value), ")
        case .Node(let value, let leftNode, let rightNode):
            if leftNode != nil {
                leftNode!.walk()
            }
            print("\(value) ")
            if (rightNode != nil) {
                rightNode!.walk()
            }
        }
    }
}

如果我运行以下测试:

    var tree = Tree();
    tree.walk()

    tree.insert(100)
    tree.walk()

    tree.insert(50)
    tree.walk()

    tree.insert(150)
    tree.walk()

    tree.insert(25)
    tree.walk()

输出是:

    Empty

    100

    50,
    100

    50,
    100,
    150

    50,
    100,
    150

25 值没有被添加到树中

(这段代码有点不雅，这只是第一次迭代，其中有几个丑陋的部分可以改进和美化。等待递归枚举功能添加到 Xcode beta 中)。

Answer 1

因为您正在改变内部节点，而这实际上是在创建它们的副本。该副本永远不会插入到树中，它只是在修改后被丢弃。如果在插入 l 和 r 后重新插入这些节点(使用 self = .Node(currentNodeValue, l, rightNode) 和 self = .Node(currentNodeValue, leftNode, r) respectively) 然后整个树将得到更新。这是一个按值/按引用的问题。