Swift二進制搜索樹搜索

我想實現一個存儲單詞列表的BST。我知道我的樹結構是正確的，因爲當我嘗試遍歷並按順序打印時，列表按字母順序打印。但是，每次在我的樹中查找元素的搜索函數都會返回false。Swift二進制搜索樹搜索

func search(searchValue: String) -> Bool? { 
    if searchValue == value as! String{ 
     return true 
    } 

    if searchValue < value as! String { 
     return left?.search(searchValue: searchValue) 
    } 
    if searchValue > value as! String{ 
     return right?.search(searchValue: searchValue) 
    } 

    return false 


}

該函數在此循環中調用。每個不在BST中的單詞都應附加到數組。目前沒有單詞被添加到數組中。輸入數組是一個包含所有要與BST進行檢查的單詞的數組。上下文

for item in arrayInput 
     { 
      let target = item.lowercased()//reversed 
      let inTree = tree.search(searchValue: target) 
      if inTree == false 
      { 
       misspelled.append(item) 
      } 
     }

更多BST類：

public class BinarySearchTree<T: Comparable> { 
     fileprivate(set) public var value: T 
     fileprivate(set) public var parent: BinarySearchTree? 
     fileprivate(set) public var left: BinarySearchTree? 
     fileprivate(set) public var right: BinarySearchTree? 


     public init(value: T) { 
      self.value = value 
     } 

     public convenience init(array: [T]) { 
      precondition(array.count > 0) 
      self.init(value: array.first!) 
      for v in array.dropFirst() { 
       insert(value: v) 
      } 
     } 

     } 
    public func insert(value: T) { 
      if value < self.value { 
       if let left = left { 
        left.insert(value: value) 
       } else { 
        left = BinarySearchTree(value: value) 
        left?.parent = self 
       } 
      } else { 
       if let right = right { 
        right.insert(value: value) 
       } else { 
        right = BinarySearchTree(value: value) 
        right?.parent = self 
       } 
      } 
     }

來源

2017-03-31 user7799235

與什麼是「作爲字符串！「到處都是？你的BST是通用的 – Alexander

另外，你對'parent'的強烈引用將導致一個保留週期，並因此導致內存泄漏。 – Alexander

我不確定如何在沒有它的情況下進行比較。沒有！字符串我收到一條消息「二元運算符<不能應用於類型'T'和'字符串' – user7799235

我做你的代碼一些改進，我們來看一看：

public class BinarySearchTree<T: Comparable> { 
    fileprivate(set) public var value: T 
    fileprivate(set) public var parent: BinarySearchTree? 
    fileprivate(set) public var left: BinarySearchTree? 
    fileprivate(set) public var right: BinarySearchTree? 


    public init(value: T) { 
     self.value = value 
    } 

    public convenience init(array: [T]) { 
     precondition(array.count > 0) 
     self.init(value: array.first!) 
     for v in array.dropFirst() { 
      insert(value: v) 
     } 
    } 

    // Refactored out common code to reduce duplicaiton 
    public func insert(value: T) { 
     let nodeToModify = value < self.value ? left : right 

     if let nodeToModify = nodeToModify { 
      nodeToModify.insert(value: value) 
     } 
     else { 
      let subtree = BinarySearchTree(value: value) 
      subtree.parent = self 
      self.left = subtree 
     } 
    } 


    // Why constrain searching to just Strings? Keep it generic to all T: Comparable 
    func search(for searchValue: T) -> Bool { 
     if searchValue == value { return true } 

     if searchValue < value { 
      return left?.search(for: searchValue) ?? false 
     } 
     if searchValue > value { 
      return right?.search(for: searchValue) ?? false 
     } 

     return false 
    } 
} 

// Move the `search` function outside of the class, and into an extension 
// with the constaint that `T == String` 
extension BinarySearchTree where T == String { 
    func search(for searchValue: String) -> Bool { 
     if searchValue == value { return true } 

     if searchValue < value { 
      return left?.search(for: searchValue) ?? false 
     } 
     if searchValue > value { 
      return right?.search(for: searchValue) ?? false 
     } 

     return false 
    } 
}

來源

2017-04-02 02:43:21 Alexander

我認爲問題是，你達到你的二叉搜索樹的葉子節點，然後返回nil。拼寫錯誤的單詞小於或大於葉的存儲值，因此您正在查找左側或右側的孩子，而這些值爲零，因此函數返回nil。

有幾種方法可以解決這個問題，但是最簡單的變化是當左邊或右邊爲零時將nales合併爲false。

func search(searchValue: String) -> Bool { 
    if searchValue == value as! String { 
     return true 
    } 

    if searchValue < value as! String { 
     return left?.search(searchValue: searchValue) ?? false 
    } 
    if searchValue > value as! String { 
     return right?.search(searchValue: searchValue) ?? false 
    } 

    return false 
}

來源

2017-03-31 20:37:47 faircloud

@vacawama引起的保留週期如何？如果搜索值<值（唯一可以輸入左側樹代碼塊的方式）比搜索值不能在右側樹中 – faircloud

'對了，我收回了我的評論，並提出你的回答 – vacawama

由於你的所有回報都是真的，所以不再需要搜索返回一個可選項 – vacawama

請找我的二叉搜索樹實施斯威夫特4

class SearchTreeNode<T: Comparable>{ 
private var element: T 
var parent: SearchTreeNode? 
var left: SearchTreeNode? 
var right: SearchTreeNode? 

init(value _element: T, parent: SearchTreeNode<T>?) { 
    element = _element 
    self.parent = parent 
} 

func value() -> T { 
    return element 
} 
} 

class BinarySearchTree<T: Comparable>{ 
var root: SearchTreeNode<T> 

init(rootValue _element: T) { 
    root = SearchTreeNode(value: _element, parent: nil) 
} 

func append(value: T) { 
    addValue(toTree: root, _element: value) 
} 

func isPresent(element: T) { 
    if let node = search(for: element, nodeToSearch: root){ 
     print(node.right?.value()) 
     print(node.left?.value()) 
     print(node.parent?.value()) 
     print("Item is presnt in search tree") 
    }else{ 
     print("Item not presnt in search tree") 
    } 
} 

private func addValue(toTree currentNode: SearchTreeNode<T>, _element: T){ 
    if currentNode.value() == _element { 
     print("Already Presnt") 
    }else if currentNode.value() > _element { 
     if currentNode.left == nil { 
      currentNode.left = SearchTreeNode(value: _element, parent: currentNode) 
     }else{ 
      addValue(toTree: currentNode.left!, _element: _element) 
     } 
    }else if currentNode.value() < _element{ 
     if currentNode.right == nil { 
      currentNode.right = SearchTreeNode(value: _element, parent: currentNode) 
     }else{ 
      addValue(toTree: currentNode.right!, _element: _element) 
     } 
    } 
} 

private func search(for _element: T, nodeToSearch node: SearchTreeNode<T>) -> SearchTreeNode<T>?{ 
    if node.value() == _element { 
     return node 
    }else if node.value() > _element { 
     if node.left == nil { 
      return nil 
     }else{ 
      return search(for: _element, nodeToSearch: node.left!) 
     } 
    }else if node.value() < _element{ 
     if node.right == nil { 
      return nil 
     }else{ 
      return search(for: _element, nodeToSearch: node.right!) 
     } 
    }else{ 
     return nil 
    } 
} 

func getRightMostNode(forNode node: SearchTreeNode<T>) -> SearchTreeNode<T> { 
    if node.right != nil { 
     return getRightMostNode(forNode: node.right!) 
    } 
    return node 
} 

func delete(_element: T){ 
    if let node = search(for: _element, nodeToSearch: root) { 
     if (node.left != nil) && (node.right != nil) { 
      var rightMostNode = getRightMostNode(forNode: node.left!) 
      rightMostNode.right = node.right 
      node.left?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.left) : (node.parent?.right = node.left) 
     }else if (node.left != nil) { 
      node.left?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.left) : (node.parent?.right = node.left) 
     }else if (node.right != nil){ 
      node.right?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.right) : (node.parent?.right = node.right) 
     }else{ 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = nil) : (node.parent?.right = nil) 
     } 
    }else{ 
     print("Element for deletion is not present") 
    } 
} 
}

來源

2018-02-09 11:05:34

Swift二進制搜索樹搜索

回答

相關問題