二叉搜索树
概念
二叉搜索树又称二叉排序树，性质如下
- 若左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若右子树不为空，则右子树上所有节点的值都大于根节点的值
- 左右子树分别也是二叉搜索树
节点的结构体
template<class T> struct BSTreenode { //指向左子树 BSTreenode<T>* _left; //指向右子树 BSTreenode<T>* _right; T _key; //初始化节点 BSTreenode(const T& key) :_left(nullptr) , _right(nullptr) , _key(key) { } };
操作
int a[]={15,6,18,3,7,17,20,2,4,13};
插入
非递归
树为空：直接增加新的节点，赋值给根节点
树不为空：先将待插入的数值与根节点的值进行比较，若大于根节点的值，向右子树进行比较；若小于根节点的值，向左子树进行比较；若相等，则返回错误；设计一个父节点用于保存上一个节点的信息，直到节点为空停止
创建一个新节点，保存待插入的数值；如果待插入的数值比父节点的值大，则与右子树连接；如果待插入的数值比父节点的值小，则与左子树连接
bool insert(const T& key) { if (_root == nullptr) { _root = new node(key); return true; } node* parent = nullptr; node* cur = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } //相等 else { return false; } } cur = new node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
递归
bool _insertr(node*& root, const T& key) { if (root == nullptr) { root = new node(key); return true; } if (root->_key < key) { return _insertr(root->_right, key); } else if (root->_key > key) { return _insertr(root->_left, key); } else return false; }
这里需要注意的是：bool _insertr(node*& root, const T& key) 递归函数中，根节点的参数类型是引用，也就是说，将待插入节点与父节点连接时，此时的父节点也是前面节点的左节点（或右节点）的引用；例如将12插入，此时节点值为13的节点不仅是12的父节点同时还是节点值为7的节点的左节点的引用；此方法便可很好地完成连接
查找
从根节点的值开始比较，如果带查找的数字比根节点的值大，则向右子树查找；比根节点的值小，向左子树查找
最多查找树的高度次，若没找到则不存在
代码实现如下
非递归
bool find(const T& key) { node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key < key) { cur = cur->_left; } else { return true; } } return false; }
递归
bool _findr(node* root, const T& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _findr(root->_right, key); } else if (root->_key > key) { return _findr(root->_left, key); } else return true; }
删除
查找元素是否存在于二叉搜索树中，不存在返回错误，存在先查找所在节点的位置
待删除节点的种类存在三种可能：左子树为空（包括左右子树都为空），右子树为空，左右子树都不为空，具体情况具体分析
左子树为空：
如果待删除的节点是父节点的左子树，则将节点的右节点与父节点的左子树连接；如果待删除的节点是父节点的右子树，则将节点的右节点与父节点的右子树连接
右子树为空与左子树类似
左右子树都不为空：
在右子树中寻找大于待删除节点值的节点，且是最小的那个；操作：在右子树中，从根节点开始一直向左寻找节点，直到某节点的左子树为空，则找到该节点；将该节点代替待删除的节点，具体操作与上面一直
非递归
bool erase(const T& key) { node* parent = nullptr; node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { //1.左为空 if (cur->_left == nullptr) { //只存在根节点 //parent=nullptr if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; }//2.右为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; }//3.左右都不为空 else { node* parent = cur; node* minright = cur->_right; while (minright->_left) { parent = minright; minright = minright->_left; } cur->_key = minright->_key; if (minright == parent->_left) { parent->_left = minright->_right; } else { parent->_right = minright->_right; } delete minright; } } } return false; }
递归
bool _eraser(node* root, const T& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _eraser(root->_right, key); } else if (root->_key > key) { return _eraser(root->_left, key); } else { node* del = root; //1.右为空 if (root->_right == nullptr) { root = root->_left; } else if (root->_left = nullptr) { root = root->_right; } else { node* minright = root->_right; while (minright->_left) { minright = minright->_left; } swap(root->_key, minright->_key); return _erasser(root->_right, key); } delete del; return true; } }
实现
这里只实现上面没有提到的功能函数
template<class T> struct BSTreenode { BSTreenode<T>* _left; BSTreenode<T>* _right; T _key; BSTreenode(const T& key) :_left(nullptr) , _right(nullptr) , _key(key) { } }; template<class T> class BSTree { typedef BSTreenode<T> node; public: BSTree() :_root(nullptr) { } BSTree(const BSTree<T>& t) { _root = Copy(t._root); } BSTree<T>& operator=(BSTree<T> t) { swap(_root, t._root); return *this; } ~BSTree() { Destory(_root); _root = nullptr; } void Inorder() { _Inorderr(_root); cout << endl; } private: void _Inorderr(node* root) { if (root == nullptr) { return; } _Inorderr(root->_left); cout << root->_key << " "; _Inorderr(root->_right); } void Destory(node* root) { if (root == nullptr) { return; } Destory(root->_left); Destory(root->_right); delete root; } node* copy(node* root) { if (root == nullptr) { return nullptr; } node* newroot = new node(root->_key); newroot->_left = copy(root->_left); newroot->_right = copy(root->_right); return newroot; } } private: node* _root = nullptr; };
应用
K模型
K模型只有 key作为关键码，结构体中只存储了key，key作为需要搜索的值
例如：给定一个英文单词，判断该单词是否拼写正确
将词库中每个单词作为key，构建一棵二叉搜索树，在二叉搜索树中搜索该单词是否存在。若存在则拼写正确；若不存在，则拼写错误
KV模型
每个关键码key，都有与之对应的Value,<key,value> 键值对
对应的关系
英文词典中英文与中文就是KV模型，通过英文可以找到对应的中文，英文单词与其对应的中文<word,chinese>构成键值对
实例如下
KV实例
template<class K,class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; K _key; V _value; BSTreeNode(const K& key, const V& value) :_key(key) ,_value(value) ,_left(nullptr) ,_right(nullptr) { } }; template<class K,class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool insert(const K& key, const V& value) { if (_root == nullptr) { _root = new Node(key, value); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } void Inorder() { _Inorderr(_root); } void _Inorderr(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_key << " " << root->_value << endl; _Inorder(root->_right); } private: Node* _root = nullptr; };
测试
void testBSTree2() { BSTree<string, string>dict; dict.insert("east", "东"); dict.insert("west", "西"); dict.insert("south", "南"); dict.insert("north", "北"); string str; while (cin >> str) { BSTreeNode<string, string>* ret = dict.Find(str); if (ret) { cout << ret->_value << endl; } else { cout << "查无此单词" << endl; } } }
