swift二进制读写_Swift二进制搜索树

swift 二进制读写

In this tutorial, we’ll be discussing Binary trees and the implement the various operations that can be performed using it in Swift.

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

二进制搜索树 (Binary Search Tree)

A Binary Search Tree in Swift is a Binary Tree which must follow the following rules:

Swift中的Binary Search Tree是必须遵循以下规则的Binary Tree&＃xff1a;

They typically provide OLogN time for insertion and lookup.

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

Swift二进制搜索树实现 (Swift Binary Search Tree Implementation)

Let’s define the Node for a tree.

让我们为树定义节点。

class Node {var data: Tvar leftNode: Node?var rightNode: Node?init(data: T,leftNode: Node? &＃61; nil,rightNode: Node? &＃61; nil) {self.data &＃61; dataself.leftNode &＃61; leftNodeself.rightNode &＃61; rightNode}}

Let’s define the BinarySearchTree class in Swift. Here we’ll define functions to insert Nodes into the tree taking care of the BST rules:

让我们在Swift中定义BinarySearchTree类。 在这里&＃xff0c;我们将定义一些函数&＃xff0c;以将BST规则的节点插入树中&＃xff1a;

class BST {private var rootNode: Node?func addNode(_ value: T) {let node &＃61; Node(data: value)if let rootNode &＃61; self.rootNode {self.insert(rootNode, node)} else {self.rootNode &＃61; node}}private func insert(_ root: Node, _ node: Node) {if root.data > node.data {if let leftNode &＃61; root.leftNode {self.insert(leftNode, node)} else {root.leftNode &＃61; node}} else {if let rightNode &＃61; root.rightNode {self.insert(rightNode, node)} else {root.rightNode &＃61; node}}}func printTree() {self.inorder(self.rootNode)}private func inorder(_ node: Node?) {guard let _ &＃61; node else { return }self.inorder(node?.leftNode)print("\(node!.data)", terminator: " ")self.inorder(node?.rightNode)}
}

We’ve assigned the Comparable and CustomStringConvertible protocols in order to compare the values of the Nodes and print the formatted data respectively.

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

The inorder function prints the left subtree followed by the current node value, followed by right subtree

顺序函数打印左子树&＃xff0c;后跟当前节点值&＃xff0c;然后右子树

Now let’s add elements into the tree.

现在让我们将元素添加到树中。

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

The output of the tree is:

树的输出为&＃xff1a;

As you can see the values in the BST are set in a sorted order.

如您所见&＃xff0c;BST中的值是按排序顺序设置的。

在树中搜索值 (Searching a value in the tree)

extension BST {func search(value: T) {self.search(self.rootNode, value)}private func search(_ root: Node?, _ element: T) {guard let rootNode &＃61; 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 }

We’ve created a search function in the extension.
In this, we simply check the node value and based on the comparison, search it recursively in the left or right subtree.

我们在扩展程序中创建了搜索功能。
在此&＃xff0c;我们只需检查节点值&＃xff0c;然后根据比较结果&＃xff0c;在左侧或右侧子树中递归搜索。

The output of two sample runs is:

两个示例运行的输出为&＃xff1a;

删除节点 (Deleting a Node)

Implementation of Deleting a Node in a BST is a little more tricky.

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

After the node is deleted, we need to rearrange the BST so that it stays sorted.
Use the following rule for deletion:

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

This means we need to first create functions in our Node class for the minimum and maximum node of the tree.
The following illustration contains the updated class Node.

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

And now we create another extension of the BST class for the deletion function which works recursively:

现在&＃xff0c;我们为删除功能创建BST类的另一个扩展&＃xff0c;该扩展递归地起作用&＃xff1a;

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

The output when deleting the first key is:

删除第一个键时的输出为&＃xff1a;

That’s all for Swift Binary Search Tree implementation.

这就是Swift Binary Search Tree实现的全部内容。

翻译自: https://www.journaldev.com/21454/swift-binary-search-tree

swift 二进制读写