计算机专业面试基础数据结构中的二叉搜索树（BST）是什么？如何实现？

一、什么是二叉搜索树（BST）

二叉搜索树（Binary Search Tree），简称BST，是一种特殊的二叉树。它具有性质：

1. 每个节点都有一个键值（key）。

2. 左子树上所有节点的键值均小于其根节点的键值。

3. 右子树上所有节点的键值均大于其根节点的键值。

4. 左、右子树也都是二叉搜索树。

二叉搜索树是一种非常高效的查找结构，其平均查找效率为O(log n)，n为树中节点的数量。这是因为二叉搜索树具有递归性质，每次查找时都可以排除一半的节点，从而减少了查找的时间。

二、二叉搜索树的实现

下面是使用Python实现二叉搜索树的代码示例：

python

class TreeNode:

def __init__(self, key):

self.left = None

self.right = None

self.val = key

class BinarySearchTree:

def __init__(self):

self.root = None

# 插入节点

def insert(self, key):

if self.root is None:

self.root = TreeNode(key)

else:

self._insert(self.root, key)

def _insert(self, node, key):

if key < node.val:

if node.left is None:

node.left = TreeNode(key)

else:

self._insert(node.left, key)

else:

if node.right is None:

node.right = TreeNode(key)

else:

self._insert(node.right, key)

# 查找节点

def search(self, key):

return self._search(self.root, key)

def _search(self, node, key):

if node is None or node.val == key:

return node

if key < node.val:

return self._search(node.left, key)

return self._search(node.right, key)

# 删除节点

def delete(self, key):

self.root = self._delete(self.root, key)

def _delete(self, node, key):

if node is None:

return node

if key < node.val:

node.left = self._delete(node.left, key)

elif key > node.val:

node.right = self._delete(node.right, key)

else:

if node.left is None:

return node.right

elif node.right is None:

return node.left

min_larger_node = self._find_min(node.right)

node.val = min_larger_node.val

node.right = self._delete(node.right, min_larger_node.val)

return node

def _find_min(self, node):

while node.left is not None:

node = node.left

return node

# 遍历节点

def inorder_traversal(self):

self._inorder_traversal(self.root)

def _inorder_traversal(self, node):

if node:

self._inorder_traversal(node.left)

print(node.val, end=' ')

self._inorder_traversal(node.right)

# 测试代码

bst = BinarySearchTree()

bst.insert(50)

bst.insert(30)

bst.insert(20)

bst.insert(40)

bst.insert(70)

bst.insert(60)

bst.insert(80)

print("Inorder traversal of the given tree:")

bst.inorder_traversal() # 输出：20 30 40 50 60 70 80

print("\nDelete 20")

bst.delete(20)

print("Inorder traversal after deleting 20:")

bst.inorder_traversal() # 输出：30 40 50 60 70 80

print("\nDelete 30")

bst.delete(30)

print("Inorder traversal after deleting 30:")

bst.inorder_traversal() # 输出：40 50 60 70 80

print("\nDelete 50")

bst.delete(50)

print("Inorder traversal after deleting 50:")

bst.inorder_traversal() # 输出：40 60 70 80

这段代码中，我们定义了一个`TreeNode`类来表示树中的节点，以及一个`BinarySearchTree`类来实现二叉搜索树的基本操作，如插入、查找、删除和遍历。在测试代码中，我们创建了一个二叉搜索树，并进行了插入、删除和遍历操作。

三、

二叉搜索树是一种常见的二叉树结构，具有高效查找和插入的特点。在计算机专业面试中，了解二叉搜索树的基本概念和实现方法是必不可少的。通过上述代码示例，我们可以更好地理解二叉搜索树的结构和操作，为面试做好准备。