在本教程中，我们将讨论二叉树，并实现可以在Swift中使用二叉树执行的各种操作。

二进制搜索树

Swift中的Binary Search Tree是必须遵循以下规则的Binary Tree：

左子树中的所有节点的值必须小于根节点中的值。
右子树中的所有节点的值必须大于根节点中的值。
根节点的左和右子树应递归遵循上述规则。

它们通常为插入和查找提供" OLogN"时间。

Swift二进制搜索树实现

让我们为树定义节点。

class Node<T> {
  
  var data: T
  var leftNode: Node?
  var rightNode: Node?
  
  init(data: T,
       leftNode: Node? = nil,
       rightNode: Node? = nil) {
      self.data = data
      self.leftNode = leftNode
      self.rightNode = rightNode
  }

}

让我们在Swift中定义BinarySearchTree类。
其中我们将定义一些函数，以便将BST规则插入"节点"到树中：

class BST<T: Comparable & CustomStringConvertible> {
  
  private var rootNode: Node<T>?
  
  func addNode(_ value: T) {
      let node = Node(data: value)
      if let rootNode = self.rootNode {
          self.insert(rootNode, node)
      } else {
          self.rootNode = node
      }
  }
  

  private func insert(_ root: Node<T>, _ node: Node<T>) {
      if root.data > node.data {
          if let leftNode = root.leftNode {
              self.insert(leftNode, node)
          } else {
              root.leftNode = node
          }
      } else {
          if let rightNode = root.rightNode {
              self.insert(rightNode, node)
          } else {
              root.rightNode = node
          }
      }
  }
  
  func printTree() {
      self.inorder(self.rootNode)
  }

  
  private func inorder(_ node: Node<T>?) {
      guard let _ = node else { return }
      self.inorder(node?.leftNode)
      print("\(node!.data)", terminator: " ")
      self.inorder(node?.rightNode)
  }
}

我们已经分配了Comparable和CustomStringConvertible协议，以便比较Node的值并分别打印格式化的数据。

顺序函数打印左子树，后跟当前节点值，然后右子树

现在，将元素添加到树中。

let numberList : Array<Int> = [8, 2, 10, 9, 11, 1, 7]
var root = BST<Int>()
for number in numberList {
  root.addNode(number)
}
//should print sorted tree
root.printTree()

树的输出为：

如您所见，BST中的值是按排序顺序设置的。

在树中搜索值

extension BST {
  
  func search(value: T) {
      self.search(self.rootNode, value)
  }
  
  private func search(_ root: Node<T>?, _ element: T) {
      
      guard let rootNode = root else {
          print("NODE is Not available : \(element)")
          return
      }
      
      print("current root node \(rootNode.data)")
      if element > rootNode.data {
          self.search(rootNode.rightNode, element)
      } else if element < rootNode.data {
          self.search(rootNode.leftNode, element)
      } else {
          print("NODE VALUE AVAILABLE : \(rootNode.data)")
      }
  }
}

我们在扩展程序中创建了搜索功能。
在这种情况下，我们只需检查节点值，然后根据比较结果，在左侧或者右侧子树中递归搜索。

两个示例运行的输出为：

删除节点

在BST中删除节点的实现有些棘手。

删除节点后，我们需要重新排列BST，以使其保持排序状态。
使用以下规则进行删除：

删除节点后，我们用左侧子树的最大子节点或者右侧子树的最小子节点替换该节点。

这意味着我们需要首先在Node类中为树的最小和最大节点创建函数。
下图包含更新的类Node。

现在，我们为删除功能创建BST类的另一个扩展，该扩展递归地起作用：

extension BST{
  
  func deleteKey(value: T)
  {
  rootNode = deleteRec(rootNode, value)
  }
  
  /* A recursive function to insert a new key in BST */
  func deleteRec(_ root: Node<T>?, _ key: T) -> Node<T>?
  {
  /* Base Case: If the tree is empty */
      if  root == nil{
      return root
      }
  
      if key < (root?.data)! {
      root?.leftNode = deleteRec(root?.leftNode, key)
      }
      else if key > (root?.data)!{
          root?.rightNode = deleteRec(root?.rightNode, key)
          }
  else
  {
      if root?.leftNode == nil{
          return root?.rightNode
      }
      else if root?.rightNode == nil{
          return root?.leftNode
      }
      
  root?.data = (minValue(root?.rightNode))!
  root?.rightNode = deleteRec(root?.rightNode, (root?.data)!)
  }
  
  return root;
  }
  
  public func minValue(_ node: Node<T>?) -> T? {
      
      var tempNode = node
      
      while let next = tempNode?.leftNode {
          tempNode = next
      }
      return tempNode?.data
  }
  
}