Loading... 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 ##1.原理 二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)). ##2.代码实现 ###整体 ```cpp #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const double EPS = 1E-6; template<typename T>struct node { T value; node<T>* parent = nullptr; node<T>* left = nullptr; node<T>* right = nullptr; node(const T &v = 0) :value(v) { }; T operator * () { return value; } }; template<typename T> class BST { private: node<T>* root = nullptr; int SIZE = 0; public: BST() {}; BST(vector<T> v); node<T>* GetRoot() { return root; } bool empty() { return SIZE == 0; } int size() { return SIZE; } node<T>* find(const T &v); node<T>* find_predecessor(const T &v);//寻找前驱节点 node<T>* find_successor(const T &v);//寻找后继节点 node<T>* find_predecessor(node<T>* n); node<T>* find_successor(node<T>* n); void insert(const T &v); void insert(node<T>* n); void erase(node<T>* n); bool erase(const T &v); void clear(); //void traversal(node<T>* root, void(*func)(T v) = [](T v)->void {cout << value << " "; });//遍历输出所有节点 void traversal(); }; template<typename T> BST<T>::BST(vector<T> v) :BST() { for (auto n : v)//C++11支持的冒号遍历 insert(n); //auto的作用是自动选择相应的类型 return; } template<typename T> node<T>* BST<T>::find(const T &v) {//二叉搜索树的查找，只需和父节点的值比较即可找到 node<T>* temp = root; while (temp != nullptr)//temp为空时就表明没找到 { if (v == temp->value)//找到就返回 return temp; else { if (v < temp->value) temp = temp->left; else temp = temp->right; } } return nullptr; } //节点x的前驱，就是指key值小于x.key的节点中key值最大的那个 //若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点 //如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里没有x节点的祖先。 template<typename T> node<T>* BST<T>::find_predecessor(const T &v) { node<T>* n = find(v); return n == nullptr ? nullptr : find_predecessor(n); } template<typename T> node<T>* BST<T>::find_predecessor(node<T>* n) { node<T>* temp = n; if (temp->left != nullptr)//如果节点有左子树 { temp = temp->left; while (temp->right != nullptr)//找左子树中最右边的叶子 temp = temp->right; return temp; } while (temp->parent != nullptr && temp->parent->left == temp) temp = temp->parent; return temp->parent; } //节点x的后继，就是指key值大于x.key的节点中key值最小的那个 //若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点 //如果x的右子树为空，那么我们就要向上找x的第一个有左孩子且右子树里没有x节点的祖先。 template<typename T> node<T>* BST<T>::find_successor(const T &v) { node<T>* n = find(v); return n == nullptr ? nullptr : find_successor(n); } template<typename T> node <T>* BST<T>::find_successor(node<T>* n) { node<T>* temp = n; if (temp->right != nullptr)//若右子树不为空 { temp = temp->right; while (temp->left != nullptr)//找右子树中最左边的叶子 temp = temp->left; return temp; } while (temp->parent != nullptr && temp->parent->right != temp) temp = temp->parent; return temp->parent; } //新插入的节点一定会取代一个原来的叶子节点，我们只要确定被取代的是哪一个叶子节点就行了 //我们从根节点开始，利用二叉搜索树的性质比对值来向下查找，直到到达最后的叶子节点，这个节点就是要用插入节点替换的叶子节点。 template<typename T> void BST<T>::insert(const T &v) { node<T>* n = new node<T>(v); insert(n); return; } template<typename T> void BST<T>::insert(node<T>* n) { node<T>* temp = root; SIZE++; if (temp == nullptr) {//如果根节点为空，则直接插入 root = n; return; } while (true)//循环找出插入的位置 { if (temp->value > n->value) {//插入在左子树的情况 if (temp->left != nullptr) temp = temp->left;//左子树不为空则继续找 else { temp->left = n;//如果左子树为空则直接插入 n->parent = temp;//修改父节点为temp指向的节点 return; } } else {//插入右子树的情况，同上 if (temp->right != nullptr) temp = temp->right; else { temp->right = n; n->parent = temp; return; } } } return; } //删除的情况比插入复杂，一共有3种可能的情况。 //1，被删除的节点x没有NIL节点以外的孩子节点时，直接删除，修改父节点指针指向NIL节点即可。 //2，被删除的节点x只有一个孩子时，用这个孩子节点替换被删除节点的位置即可。 //3，被删除的节点x有两个孩子时，我们就要查找x节点的后继y节点，注意y节点一定在x节点的右子树中而且y节点没有左孩子，此时，我们先用y节点的右孩子代替y节点原先的位置，然后再用y节点代替x节点位置即可完成删除操作。 template<typename T> bool BST<T>::erase(const T &v) { node<T>* temp = find(v); if (temp != nullptr) erase(temp); else return false; return true; } template<typename T> void BST<T>::erase(node<T>* n) { SIZE--; node<T>* temp; if (n->left == nullptr && n->right == nullptr) temp = nullptr;//情况1：没有子节点 else if (n->left == nullptr || n->right == nullptr) {//情况2：有一个子节点 temp = n->left == nullptr ? n->right : n->left; temp->parent = n->parent;//因为temp要取代n，所以temp要完全复制n的信息。又因temp是n的一个子节点，故只需复制n的parent就够了 } else//情况3：有两个子节点 { temp = find_successor(n);//用n节点的后继y来取代n node<T>* successor_right;//后继y可能有右儿子，所以需要先用y的右儿子取代y，再让y取代n if (temp->right == nullptr)//没有右儿子的话就用nullptr来取代y successor_right = nullptr; else { successor_right = temp->right; successor_right->parent = temp->parent;//用y的右儿子取代y } if (temp->parent->left == temp)//这里用来修改y的父节点，使y的右儿子完全取代y temp->parent->left = successor_right; else temp->parent->right = successor_right; //至此，对y的处理就已经完成了。接下来就是让y取代n了 //这一步只需要把y的值赋值给n，然后删除y就好了 n->value = temp->value; delete temp; return; } //情况一和情况二到此为止取代n节点的temp已经确定，而且当temp不是nullptr的时候，temp也已经复制了必要的n的属性，剩下的就是让n的父节点指向temp了 //注意被删除的节点有可能是根节点，所以当我们发现被删除的是根节点时，不需要让n的父节点指向temp，因为n没有父节点了，但是这个时候必须修改root指针的指向 if (n->parent != nullptr) { if (n->parent->left == temp) n->parent->left = temp; else n->parent->right = temp; } else root = temp; delete n; return; } template<typename T>void BST<T>::clear() { if (root == nullptr) return; queue<node<T>*> q; q.push(root); while (!q.empty()) { node<T>* temp = q.front(); q.pop(); if (temp->left != nullptr) q.push(temp->left); if (temp->right != nullptr) q.push(temp->right); delete temp; SIZE--; } root = nullptr; return; } //第一个参数是为了进行递归而设立的。 //第二个参数是一个函数指针，这个函数指针指向一个没有返回值同时有一个int类型参数的函数， //并且我用lambda表达式给这个函数指针赋了一个默认值，这个默认函数的功能是输出参数k，用来遍历输出每一个节点的值， //大家可以用别的lambda表达式或者函数来覆盖这个默认值，以达到定制功能的目的 //template<typename T> void BST<T>::traversal(node<T>* root, void(*func)(T v)) //{ // if (root = nullptr) // return; // // traversal(root->left); // func(root->value); // traversal(root->right); // // return; //} template<typename T> void BST<T>::traversal() {//广搜遍历输出 if (root == nullptr) return; queue<node<T>*> q; q.push(root); while (!q.empty()) { node<T>* temp = q.front(); q.pop(); cout << temp->value << " "; if (temp->left != nullptr) q.push(temp->left); if (temp->right != nullptr) q.push(temp->right); } return; } ``` 输出的那一块注释掉的是lambda语法写的输出。因为我这里写的是模板类，导致会有错误。把所有和模板有关的改成int就可以用了。 前中后序遍历后面再写吧。 最后修改：2019 年 04 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏