二叉搜索树【C++】

二叉搜索树BSTBinary Search Tree,也称二叉排序树或二叉查找树二叉搜索树一棵二叉树可以为空如果不为空则满足以下性质1. 非空左子树的所有键值小于其根节点的键值2. 非空右子树的所有键值大于其根节点的键值3. 左、右子树都是二叉搜索树。左子树比根小右子树比根大默认定义搜索树不允许冗余1 插入templateclass K struct BSTreeNode { BSTreeNodeK* _left; BSTreeNodeK* _right; K _key; }; templateclass K class BSTree { typedef BSTreeNodeK Node; bool Insert(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 false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了没有形成链接 //cur new Node(key); //return true; //链接方法 //找到空位置还需要找到该节点的父亲位置 } private: Node* _root nullptr; };当找到空位置还需要找到该节点的父亲位置就是cur 每次往下寻找的时候把cur给父节点。也就是记录cur每次走过的上一个位置#pragma once templateclass K struct BSTreeNode { BSTreeNodeK* _left; BSTreeNodeK* _right; K _key; }; templateclass K class BSTree { typedef BSTreeNodeK Node; bool Insert(const K 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 { return false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了没有形成链接 //cur new Node(key); //return true; //链接方法 //找到空位置还需要找到该节点的父亲位置 cur new Node(key); if (key parent-_key) { parent-_right cur; } else { parent-_key cur; } } private: Node* _root nullptr; };插入中序遍历#pragma once #include iostream using namespace std; templateclass K struct BSTreeNode { BSTreeNodeK* _left; BSTreeNodeK* _right; K _key; //构造 BSTreeNode(const K key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; templateclass K class BSTree { public: typedef BSTreeNodeK Node; bool Insert(const K 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-_right; } else if(cur-_key key) { parent cur; cur cur-_left; } else { return false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了没有形成链接 //cur new Node(key); //return true; //链接方法 //找到空位置还需要找到该节点的父亲位置 cur new Node(key); //判断链接在左边还是在右边 if (key parent-_key) { parent-_right cur; } else { parent-_left cur; } return true; } //中序遍历 //通常使用 友元或者缺省参数或者套一层 //这里使用套一层 void InOrder() { _InOrder(_root); } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } Node* _root nullptr; }; void TestBSTree1() { int a[] {10,20,22,8}; BSTreeint t1; for (auto e : a) { t1.Insert(e); } t1.InOrder(); }2 查找//查找 bool Find(const K key) { Node* cur _root; while (cur) { if (key cur-_key) { cur cur-_right; } else if (key cur-_key) { cur cur-_left; } else { return true; } } return false; }3 删除删除分以下几种情况a 删除的节点没有孩子找到该节点后先记录该节点的父节点然后再把节点删除同时把父节点指向删除节点的指针置空b 删除的节点有1个孩子直接让删除节点的父节点直接指向删除节点的孩子节点即可c 删除的节点有2个孩子替换法找到一个节点的值替代你该节点应该是 左子树最大节点或者右子树的最小节点删除节点流程1 先找到删除节点2 判断删除节点的哪个子树为空a 删除节点的左子树为空然后再去判断删除节点是父节点的左边还是右边i 父节点的左边让父节点的左边指向删除节点的右子树ii 父节点的右边让父节点的右边指向删除节点的右子树b 删除节点的右子树为空然后再去判断删除节点是父节点的左边还是右边b1 父节点的左边让父节点的左边指向删除节点的左子树b2 父节点的右边让父节点的右边指向删除节点的左子树c 删除节点的左右子树都不为空c1 找到一个节点的值替代你该节点应该是 左子树最大节点或者右子树的最小节点//找到删除节点,当左子树为空 if (cur-_left nullptr) { //删除节点的左子树为空需要判断删除节点是父节点的左边还是右边 if (cur parent-_left) { parent-_left cur-_right; } else { //如果是父节点的右边 parent-_right cur-_right; } delete cur; } else if (cur-_right nullptr) { //删除节点的右子树为空 if (cur parent-_left) { parent-_left cur-_left; } else { parent-_right cur-_left; } delete cur; }参考代码如下else { //左右都不为空使用替换法进行删除 //找到一个节点的值替代你该节点应该是 左子树最大节点或者右子树的最小节点 //查找右子树的最左节点 //这里使用右子树的最小节点 Node* rightMinParent nullptr; Node* rightMin cur-_right; //删除节点的右子树一直往左边走 while (rightMin-_left) { rightMinParent rightMin; rightMin rightMin-_left; } //注意这里不能 交换删除节点的值然后再去删除节点这样找不到节点 swap(cur-_key,rightMin-_key); rightMinParent-_left rightMin-_right; delete rightMin; }但是该代码逻辑存在一个bug:这里的一个解决方法是先直接让rightMinParent指向当前cur节点之后再单独判断处理rightMinParent搜索二叉树删除的完整实现代码//删除 bool Erase(const K key) { //删除节点需要记录一下父亲节点 Node* parent nullptr; Node* cur _root; while (cur) { if (key cur-_key) { parent cur; cur cur-_right; } else if (key cur-_key) { parent cur; cur cur-_left; } else { //找到删除节点,当左子树为空 if (cur-_left nullptr) { if (cur _root) //避免 parent nullptr { _root cur-_right; } else { //删除节点的左子树为空需要判断删除节点是父节点的左边还是右边 if (cur parent-_left) { parent-_left cur-_right; } else { //如果是父节点的右边 parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { //if(parent nullptr) if (cur _root) { _root cur-_left; } else { //删除节点的右子树为空 if (cur parent-_left) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { //删除节点的左右子树都不为空使用替换法进行删除 //找到一个节点的值替代你该节点应该是 左子树最大节点或者右子树的最小节点 //查找右子树的最左节点 //这里使用右子树的最小节点 Node* rightMinParent cur; Node* rightMin cur-_right; //删除节点的右子树一直往左边走 while (rightMin-_left) { rightMinParent rightMin; rightMin rightMin-_left; } //注意这里不能 交换删除节点的值然后再去删除节点这样找不到节点 swap(cur-_key, rightMin-_key); if (rightMinParent-_left rightMin) { rightMinParent-_left rightMin-_right; } else { rightMinParent-_right rightMin-_right; } //rightMinParent-_left rightMin-_right; //error 直接使用容易出现野指针问题 delete rightMin; } return true; } } return false; //没有找打要删除的节点 }搜索二叉树的时间复杂度平均O(logN)