什么是二叉搜索树?二叉搜索树的查找、插入、删除实现

一、什么是二叉搜索树

二叉搜索树（Binary Search Tree）又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: （1）若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 （2）若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 （3）它的左右子树也分别为二叉搜索树 二叉搜索树拥有很高的查找效率（一般情况下），树中最左节点为最小元素，最右节点为最大元素

二、二叉搜索树的实现（查找、插入、删除）

代码如下：

#include<iostream> using namespace std; //二叉搜索树节点 template <class T> struct BSTNode { BSTNode<T>* left; BSTNode<T>* right; T _val; BSTNode(const T& val) :left(nullptr) , right(nullptr) , _val(val) {} }; template <class T> class BSTree { public: typedef BSTNode<T> Node; typedef Node* pNode; bool find(const T& val) { pNode cur = root; while (cur) { if (cur->_val == val) return true; else if (cur->_val > val) cur = cur->left; else cur = cur->right; } return false; } bool insert(const T& val) { //如果树为空 if (root == nullptr) { root = new Node(val); return true; } pNode cur = root; pNode parent = nullptr; //记录父节点的位置 //找到合适的位置进行插入 while (cur) { parent = cur; //更新父节点位置 if (cur->_val == val) return false; //无法插入相同值的节点 else if (cur->_val > val) cur = cur->left; else cur = cur->right; } cur = new Node(val); //比较父节点与插入节点的值大小,确定插入哪边 if (parent->_val > val) parent->left = cur; else parent->right = cur; return true; } bool erase(const T& val) { //空树不能删除 if (root == nullptr) return false; pNode cur = root; pNode parent = nullptr; while (cur) { if (cur->_val == val) break; else if (cur->_val > val) { parent = cur; cur = cur->left; } else { parent = cur; cur = cur->right; } } //判断cur是否存在 if (cur == nullptr) return false; else { //被删除节点的左子树为空 if (cur->left == nullptr) { //分两种情况: cur是不是根节点 if (cur != root) { if (parent->left == cur) parent->left = cur->right; else parent->right = cur->right; } else root = cur->right; //更新根节点 delete cur; cur = nullptr; } //被删除节点的右子树为空 else if (cur->right == nullptr) { if (cur != root) { if (parent->left == cur) parent->left = cur->left; else parent->right = cur->left; } else root = cur->left; delete cur; cur = nullptr; } //两边都不为空 else { //找左子树的最右节点或右子树的最左节点,这里选前者 pNode next = cur->left; pNode parent = cur; while (next->right) { parent = next; next = next->right; } //交换值 cur->_val = next->_val; if (parent->left == next) parent->left = next->left; else parent->right = next->left; //删除找的节点 delete next; next = nullptr; } return true; } } void _inOrder(pNode root) { if (root) { _inOrder(root->left); cout << root->_val << " "; _inOrder(root->right); } } void inOrder() { _inOrder(root); cout << endl; } private: pNode root = nullptr; }; void testBSTree() { BSTree<int> bst; bst.insert(5); bst.insert(7); bst.insert(2); bst.insert(1); bst.insert(9); bst.insert(6); bst.insert(4); bst.insert(10); bst.insert(0); bst.inOrder(); bst.erase(9); //没有左子树的情况 bst.erase(1); //没有右子树的情况 bst.erase(7); //两边都有节点的情况 bst.inOrder(); } int main() { testBSTree(); return 0; }

运行截图：

二叉搜索树的中序遍历是一个递增的序列。