二叉搜索树：数据结构之美

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树，它的每个节点具有以下性质：左子树上的所有节点的键值均小于它的根节点的键值；右子树上所有节点的键值均大于它的根节点的键值。这种结构使得二叉搜索树成为了高效查找、插入和删除数据的理想选择。

基础知识

定义

二叉搜索树是一种二叉树，其中每个节点包含一个键值、一个指向左子树的引用以及一个指向右子树的引用。左子树中的所有节点的键值小于该节点的键值，而右子树中的所有节点的键值大于该节点的键值。

性质

唯一性：给定一组键值，存在唯一的二叉搜索树。
中序遍历：对二叉搜索树进行中序遍历时，返回的键值序列是递增排序的。
查找效率：在理想情况下，查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中节点的数量。

操作详解

插入节点

插入操作涉及比较新键值与树中节点的键值，并沿着树向下移动，直到找到合适的位置。

TreeNode* BinarySearchTree::_insert(TreeNode* node, int key) {if (node == nullptr) {return new TreeNode(key);}if (key < node->key) {node->left = _insert(node->left, key);} else if (key > node->key) {node->right = _insert(node->right, key);}return node;
}void BinarySearchTree::insert(int key) {root = _insert(root, key);
}

删除节点

删除操作分为三种情况：

节点没有子节点（叶节点）。
节点有一个子节点。
节点有两个子节点。

TreeNode* BinarySearchTree::_minValueNode(TreeNode* node) {TreeNode* current = node;while (current && current->left != nullptr) {current = current->left;}return current;
}TreeNode* BinarySearchTree::_remove(TreeNode* node, int key) {if (node == nullptr) {return node;}if (key < node->key) {node->left = _remove(node->left, key);} else if (key > node->key) {node->right = _remove(node->right, key);} else {if (node->left == nullptr) {TreeNode* temp = node->right;delete node;return temp;} else if (node->right == nullptr) {TreeNode* temp = node->left;delete node;return temp;}TreeNode* temp = _minValueNode(node->right);node->key = temp->key;node->right = _remove(node->right, temp->key);}return node;
}void BinarySearchTree::remove(int key) {root = _remove(root, key);
}

查找节点

查找操作用于确定树中是否存在某个键值。

bool BinarySearchTree::_find(TreeNode* node, int key) const {if (node == nullptr) {return false;}if (key == node->key) {return true;} else if (key < node->key) {return _find(node->left, key);} else {return _find(node->right, key);}
}bool BinarySearchTree::find(int key) const {return _find(root, key);
}

遍历

前序遍历

前序遍历的顺序是根节点、左子树、右子树。

void BinarySearchTree::_preorderTraversal(TreeNode* node) const {if (node != nullptr) {std::cout << node->key << " ";_preorderTraversal(node->left);_preorderTraversal(node->right);}
}void BinarySearchTree::preorderTraversal() const {_preorderTraversal(root);
}

中序遍历

中序遍历的顺序是左子树、根节点、右子树。对于二叉搜索树，这将返回一个升序的键值序列。

void BinarySearchTree::_inorderTraversal(TreeNode* node) const {if (node != nullptr) {_inorderTraversal(node->left);std::cout << node->key << " ";_inorderTraversal(node->right);}
}void BinarySearchTree::inorderTraversal() const {_inorderTraversal(root);
}

后序遍历

后序遍历的顺序是左子树、右子树、根节点。

void BinarySearchTree::_postorderTraversal(TreeNode* node) const {if (node != nullptr) {_postorderTraversal(node->left);_postorderTraversal(node->right);std::cout << node->key << " ";}
}void BinarySearchTree::postorderTraversal() const {_postorderTraversal(root);
}