Swift二进制搜索树搜索

Question

我想实现一个存储单词列表的BST。我知道我的树结构是正确的，因为当我尝试遍历并按顺序打印时，列表按字母顺序打印。但是，每次在我的树中查找元素的搜索函数都会返回false。

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

Answer 1

我做你的代码一些改进，我们来看一看：

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

Answer 2

我认为问题是，你达到你的二叉搜索树的叶子节点，然后返回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 
} 

Answer 3

请找我的二叉搜索树实施斯威夫特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") 
    } 
} 
}