Thực hiện cây nhị phân bằng Swift enum

Question

Tôi đang thực hiện một số thí nghiệm với Swift enums để trở nên quen thuộc hơn với chúng và đã triển khai một cây nhị phân thô sơ. Nó hoạt động khi thêm tối đa ba mục, nhưng thêm nhiều hơn nữa mà không thay đổi nó và tôi không thể thấy tại sao nó không hoạt động.

Dưới đây là các mã:

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

Và nếu tôi chạy thử nghiệm sau đây:

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() 

Đầu ra là:

Empty 

    100 

    50, 
    100 

    50, 
    100, 
    150 

    50, 
    100, 
    150 

Giá trị 25 là không nhận được thêm vào cây

(Mã này là một chút không thích hợp, nó chỉ là lần lặp đầu tiên, có một số phần xấu xí trong đó có thể được cải thiện và làm đẹp. Đang chờ chức năng enum đệ quy được thêm vào bản Xcode beta).

Answer 1

Tôi biết bạn đã có câu trả lời, nhưng tôi thực sự thích triển khai của bạn và nghĩ rằng tôi sẽ cung cấp mã để triển khai giải pháp @ Wain và cũng hợp lý hóa một số logic lồng nhau if-else.

Nó bao gồm một sửa đổi nhỏ cho các giao thức, do đó insert trả về một giá trị:

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

Và sau đó insert chức năng có thể được viết lại như thế này:

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

    case .Leaf(let currentNodeValue): 
     let newTree = Tree(value: value) 
     self = value < currentNodeValue 
      ? .Node(currentNodeValue, newTree, .None) 
      : .Node(currentNodeValue, .None, newTree) 

    case var .Node(currentNodeValue, leftNode, rightNode): 
     self = value < currentNodeValue 
      ? .Node(currentNodeValue, leftNode?.insert(value) ?? Tree(value: value), rightNode) 
      : .Node(currentNodeValue, leftNode, rightNode?.insert(value) ?? Tree(value: value)) 
    } 
    return self 
} 

Answer 2

Vì bạn đang đột biến các nút nội bộ và thực tế là tạo một bản sao của chúng. Bản sao đó không bao giờ được đưa vào cây, nó chỉ bị vứt đi sau khi được sửa đổi. Nếu sau khi chèn vào l và r bạn lắp lại các nút đó (với self = .Node(currentNodeValue, l, rightNode) và self = .Node(currentNodeValue, leftNode, r) tương ứng) thì toàn bộ cây sẽ được cập nhật. Đó là vấn đề theo giá trị/theo tham chiếu.