Loading... 今天重写了一遍二叉搜索树，在这里记录一下吧。 ##1.二分查找法定义 > 二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 ##2.二叉查找树（Binary Search Tree）基础 二叉查找树也可叫做二分查找树。 它不仅可以查找数据，还可以高效地插入、删除数据。 特点：每个节点的key值大于左子节点，小于右子节点。 !> 注意它不一定是完全的二叉树。 二叉查找树有两个属性： - 所有节点都比左子树中的节点大 - 所有节点都小于右子树中的节点 通过这两个属性，可以推断出以下结论： - 二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾（如图数字 3 ） - 二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾（如图数字 28 ） ##3.代码实现 ```cpp #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; struct Node { int value; Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; Node(const int &v = 0) :value(v) { }; int operator * () { return value; } }; class BST { private: Node* root = nullptr; int SIZE = 0; /*查找节点前驱，后继*/ Node* find_predecessor(Node* n); Node* find_successor(Node* n); /*插入，删除*/ bool insert(Node* n); bool erase(Node* n); /*三序遍历*/ void __preorderTraversal(Node* node, vector<int> &res); void __inorderTraversal(Node* node, vector<int> &res); void __postorderTraversal(Node* node, vector<int> &res); public: /*构造，析构*/ BST() :root(nullptr), SIZE(0) { } BST(vector<int> data); ~BST(); /*二叉搜索树的信息*/ Node* begin() { return root; } bool empty() { return SIZE == 0; } int size() { return SIZE; } /*查找*/ Node* find(const int &data); Node* find_predecessor(const int &v);//寻找前驱节点 Node* find_successor(const int &v);//寻找后继节点 /*插入，删除*/ bool insert(const int &v); bool erase(const int &v); void clear(); /*三序遍历*/ vector<int> preorderTraversal(Node* node); vector<int> inorderTraversal(Node* node); vector<int> postorderTraversal(Node* node); /*其他*/ void traversal(Node* node, void(*func)(int data) = [](int data)->void {cout << data << " "; });//遍历输出所有节点 }; BST::BST(vector<int> data) { for (auto n : data)//C++11支持的冒号遍历 insert(n); //auto的作用是自动选择相应的类型 return; } BST::~BST() { clear(); return; } /***************************************************************** Function:find_predecessor Description：查找节点的前驱。 节点x的前驱，就是指value小于x节点中value最大的那个节点 若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点 如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里没有 x节点的祖先。 *****************************************************************/ Node * BST::find_predecessor(const int & data) { Node* tmp = find(data); return tmp == nullptr ? nullptr : find_predecessor(tmp); } Node * BST::find_predecessor(Node * n) { Node* tmp = n; if (tmp->left != nullptr) {//当左子树不为空的时候 tmp = tmp->left; while (tmp->right != nullptr) tmp = tmp->right;//寻找左子树中最右边的节点 return tmp; } while (tmp->parent != nullptr && tmp->parent->left == tmp) tmp = tmp->parent;//找x的第一个有右孩子且左子树里没有x节点的祖先 return tmp->parent; } /***************************************************************** Function:find_predecessor Description：查找节点的后继。 节点x的后继，就是指value大于x节点中value最小的那个节点 若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点 如果x的右子树为空，那么我们就要向上找x的第一个有左孩子且右子树里 没有x节点的祖先。 *****************************************************************/ Node * BST::find_successor(const int & data) { Node* tmp = find(data); return tmp == nullptr ? nullptr : find_successor(data); } Node * BST::find_successor(Node * n) { Node* tmp = n; if (tmp->right != nullptr) { tmp = tmp->right; while (tmp->left != nullptr) tmp = tmp->left; return tmp; } while (tmp->parent != nullptr && tmp->parent->right != tmp) tmp = tmp->parent;//向上找x的第一个有左孩子且右子树里没有x节点的祖先 return tmp->parent; } /***************************************************************** Function:find Description：查找值为data的节点。 *****************************************************************/ Node * BST::find(const int & data) { Node* tmp = root; while (tmp != nullptr && tmp->value != data) tmp = data > tmp->value ? tmp->right : tmp->left; return tmp; } /***************************************************************** Function:insert Description：向树中插入值data。 新插入的节点一定会取代一个原来的叶子节点，我们只要确定被取代的是 哪一个叶子节点就行了。 我们从根节点开始，利用二叉搜索树的性质比对值来向下查找，直到到达 最后的叶子节点，这个节点就是要用插入节点替换的叶子节点。 *****************************************************************/ bool BST::insert(const int & data) { Node* tmp = new Node(); return insert(tmp); } bool BST::insert(Node * n) { Node* tmp = n; SIZE++; if (root == nullptr) { root = n;//如果根节点为空则直接插入 return true; } while (true)//循环找出插入点 { if (tmp->value > n->value) {//插入在左子树的情况 if (tmp->left != nullptr) tmp = tmp->left;//左子树不为空则继续找 else { tmp->left = n;//如果左子树为空则直接插入 n->parent = tmp;//修改父节点为tmp指向的节点 return true; } } else {//插入右子树的情况，同上 if (tmp->right != nullptr) tmp = tmp->right; else { tmp->right = n; n->parent = tmp; return true; } } } return false; } /***************************************************************** Function:erase Description：从二叉树中删除node节点，返回删除是否成功。 删除的情况比插入复杂，一共有3种可能的情况。 1. 被删除的节点x没有nullptr节点以外的孩子节点时，直接删除，修改 父节点指针指向nullptr节点即可。 2. 被删除的节点x只有一个孩子时，用这个孩子节点替换被删除节点的位 置即可。 3. 被删除的节点x有两个孩子时，我们就要查找x节点的后继y节点，注意 y节点一定在x节点的右子树中而且y节点没有左孩子，此时，我们先用y节 点的右孩子代替y节点原先的位置，然后再用y节点代替x节点位置即可完 成删除操作。 *****************************************************************/ bool BST::erase(Node * n) { if (n == nullptr) return false; SIZE--; Node* tmp = n; if (n->left == nullptr && n->right == nullptr)//没有子节点 tmp = nullptr; else if (n->left == nullptr || n->right == nullptr) {//一个子节点 tmp = n->left == nullptr ? n->right : n->left; tmp->parent = n->parent; /*因为tmp要取代n，所以tmp要完全复制n的信息。 又因tmp是n的一个子节点，故只需复制n的parent就够了*/ } else//有两个子节点 { tmp = find_successor(n);//用n节点的后继y来取代n Node* successor_right; //后继y可能有右儿子，所以需要先用y的右儿子取代y，再让y取代n if (tmp->right == nullptr)//没有右儿子的话就用nullptr来取代y successor_right = nullptr; else { successor_right = tmp->right; successor_right->parent = tmp->parent;//用y的右儿子取代y } /* 这里用来修改y的父节点，使y的右儿子完全取代y */ if (tmp->parent->left == tmp) tmp->parent->left = successor_right; else tmp->parent->right = successor_right; /* 至此，对y的处理就已经完成了。接下来就是让y取代n了 这一步只需要把y的值赋值给n，然后删除y就好了 */ n->value = tmp->value; delete tmp; return true; } /* 情况一和情况二到此为止取代n节点的tmp已经确定，而且当tmp不是 nullptr的时候，tmp也已经复制了必要的n的属性，剩下的就是让n的 父节点指向tmp了 注意被删除的节点有可能是根节点，所以当我们发现被删除的是根节点 时，不需要让n的父节点指向tmp，因为n没有父节点了，但是这个时候 必须修改root指针的指向 */ if (n->parent != nullptr) { if (n->parent->left == tmp) n->parent->left = tmp; else n->parent->right = tmp; } else root = tmp; delete n; return true; } bool BST::erase(const int & data) { return erase(find(data)); } /***************************************************************** Function:clear Description：清空树。 *****************************************************************/ void BST::clear() {//这里我用了广搜的思想，也可以使用递归 if (root == nullptr) return; queue<Node*> q; q.push(root); while (!q.empty()) { Node* tmp = q.front(); q.pop(); if (tmp->left != nullptr) q.push(tmp->left); if (tmp->right != nullptr) q.push(tmp->right); delete tmp; SIZE--; } root = nullptr; return; } /***************************************************************** Function:traversal Description：遍历输出二叉搜索树。 这里解释一下这个lambda语法: 第一个参数是为了进行递归而设立的。 第二个参数是一个函数指针，这个函数指针指向一个没有返回值同时有一个int类型参数 的函数， 并且我用lambda表达式给这个函数指针赋了一个默认值，这个默认函数的功能是输出参 数k，用来遍历输出每一个节点的值， 大家可以用别的lambda表达式或者函数来覆盖这个默认值，以达到定制功能的目的 *****************************************************************/ void BST::traversal(Node* node, void(*func)(int data)) { if (node = nullptr) return; traversal(node->left); func(node->value); traversal(node->right); return; } /***************************************************************** Function:preorderTraversal Description：前序遍历。 *****************************************************************/ void BST::__preorderTraversal(Node* node, vector<int> &res) { if (node) { res.push_back(node->value); __preorderTraversal(node->left, res); __preorderTraversal(node->right, res); } return; } vector<int> BST::preorderTraversal(Node* node) { vector<int> res; __preorderTraversal(node, res); return res; } /***************************************************************** Function:inorderTraversal Description：中序遍历。 *****************************************************************/ void BST::__inorderTraversal(Node* node, vector<int> &res) { if (node) { __inorderTraversal(node->left, res); res.push_back(node->value); __inorderTraversal(node->right, res); } return; } vector<int> BST::inorderTraversal(Node* node) { vector<int> res; __inorderTraversal(node, res); return res; } /***************************************************************** Function:postorderTraversal Description：后序遍历。 *****************************************************************/ void BST::__postorderTraversal(Node* node, vector<int> &res) { if (node) { __postorderTraversal(node->left, res); __postorderTraversal(node->right, res); res.push_back(node->value); } return; } vector<int> BST::postorderTraversal(Node* node) { vector<int> res; __postorderTraversal(node, res); return res; } ``` 最后修改：2019 年 04 月 10 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏