国内比较好的软文网站,网上做一道题2元的网站,建筑工程教育网,宽带推广方案搜索二叉树的概念
搜索二叉树规则#xff08;左小右大#xff09;#xff1a; 非空左子树的键值小于其根节点的键值非空右子树的键值大于其根节点的键值左右子树均为搜索二叉树 如图#xff1a; 在搜索时#xff0c;若大于根#xff0c;则去右子树寻找#xff1b;若小…搜索二叉树的概念
搜索二叉树规则左小右大 非空左子树的键值小于其根节点的键值非空右子树的键值大于其根节点的键值左右子树均为搜索二叉树 如图 在搜索时若大于根则去右子树寻找若小于根则去左子树寻找。直到找到或为空结束。在理想状态下只需查找树的高度次。 代码实现
#pragma once
#includeiostream
using namespace std;//key版本
namespace key
{templateclass Tstruct BSTreeNode{BSTreeNodeT* _left;BSTreeNodeT* _right;T _key;BSTreeNode(const T key):_left(nullptr),_right(nullptr),_key(key){}};templateclass Tclass BSTree{typedef BSTreeNodeT Node;public: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-_left cur;}else{parent-_right cur;}return true;}Node* find(const T key){Node* cur root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return cur;}}return nullptr;}bool Erase(const T key){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{if (cur-_left nullptr){if (cur root){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 (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);//假设没有进循环那么rightMin cur-_right所以要判断一下。if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}void InOrder(){_InOrder(root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}Node* root nullptr;};
}//key_value版本
namespace key_value
{templateclass T, class Vstruct BSTreeNode{BSTreeNodeT,V* _left;BSTreeNodeT,V* _right;T _key;V _value;BSTreeNode(const T key,const V value V()):_left(nullptr), _right(nullptr), _key(key),_value(value){}};templateclass T, class Vclass BSTree{typedef BSTreeNodeT,V Node;public:bool Insert(const T 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-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{return false;}}cur new Node(key, value);;if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}Node* find(const T key){Node* cur root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return cur;}}return nullptr;}bool Erase(const T key){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{if (cur-_left nullptr){if (cur root){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 (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;//找cur右子树最小的值while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);swap(cur-_value, rightMin-_value);//假设没有进循环那么rightMin cur-_right所以要判断一下。if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}void InOrder(){_InOrder(root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key root-_value endl;_InOrder(root-_right);}Node* root nullptr;};}
Insert函数详解
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-_left cur;}else{parent-_right cur;}return true;} 1若根节点为空为其新建new一个节点。 2若根节点不为空则根据二叉树定义大于当前根的键值进右子树小于当前根的键值进左子树去寻找合适的位置新建节点。出现等于即重复的情况不插入。 3新节点连接入树时要检查他是parent的左节点还是右节点判断完毕后再连接。 Erase函数详解
bool Erase(const T key){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//找到删除目标{//假设目标左子树为空if (cur-_left nullptr){if (cur root){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 (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);//假设没有进循环那么rightMin cur-_right所以要判断一下。if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}1第一步寻找删除目标有可能是根节点找不到返回false表示删除失败。
2删除 目标左子树为空目标右子树为空目标左右子树都不为空 左子树为空
删除目标不是根节点时让目标的父节点指向他的右子树。当然也要判断目标是他的父节点的左子树还是右子树。
为父节点的左子树 为父节点的右子树 目标为根节点 右子树为空的情况只是与左子树为空方向相反不过多赘述
左右子树都不为空时
交换 目标的键值 和 目标的右子树中的最左节点的键值 然后让最左节点的父节点指向最左节点的右子树因为是最左节点所以左子树一定为空右子树可能为空可能不为空最后将这个最左节点删除。 让最左节点的父节点指向最左节点的右子树前也要判断该最左节点是否是其父节点的左子树因为有可能出现图中的情况。
此时右子树最左节点是7但他却是父节点的右子树。此时是父节点的右指向最左节点的右子树而不是父节点的左去指向。 原理
删除后要保持树还是搜索二叉树。那么首先先理清一下节点键值的关系。 所以我们是希望保持如图的节点关系那么右子树的最左节点满足做根节点条件。
因为在任意树中都有 右大于根大于左 所以该树最左节点存储最小键值。 特殊存储情况
当出现顺序插入时会呈现出这样的情况这个时候遍历的时间复杂度就退化到了O(n)此时搜索二叉树就失去了意义。不过平衡二叉树和红黑树解决了高度不平衡导致搜索效率下降的问题。
