数据库和网站建设的论文,wordpress二级页面打开报错,dw个人网站制作,专题学习网站模板目录
搜索二叉树概念
模拟实现搜索二叉树 插入函数实现 插入函数实现#xff08;递归#xff09;
查找函数实现 删除函数实现 删除函数实现#xff08;递归#xff09;
中序遍历实现 拷贝构造函数实现 析构函数实现 赋值重载 我们在最开始学习二叉树的时候#xff0c;…目录
搜索二叉树概念
模拟实现搜索二叉树 插入函数实现 插入函数实现递归
查找函数实现 删除函数实现 删除函数实现递归
中序遍历实现 拷贝构造函数实现 析构函数实现 赋值重载 我们在最开始学习二叉树的时候最开始接触的就是堆但那个结构上并不是真正的二叉树后来又借助链表实现了真正的结构上的二叉树二叉树不仅仅只是在OJ题上刁难我们其实当实现了一定的节点逻辑之后也可以形成效率极高的数据结构这个二叉树就是搜索二叉树。 搜索二叉树概念 对于一颗搜索二叉树来说它的节点内存储的值遵循如下的规则
右子树节点的值一定大于当前节点的值左子树节点的值一定小于当前节点的值而对于其结构来说
搜索二叉树不允许已存在于二叉树内部的值再次插入搜索二叉树的左右子树也必须是搜索二叉树 数据插入的顺序不同搜索二叉树的形状也会不同 这样的结构让搜索二叉树的效率在平衡的情况下效率变得非常的高
最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log_2 N但是当插入数据是有序的时候搜索二叉树会退化成单叉树 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N其整体的树结构以及逻辑就差不多如上所述了接下来就是模拟实现。 模拟实现搜索二叉树 插入函数实现 首先先定义一下节点的结构我们加入模板。 templateclass Kstruct BSNode{BSNodeK* _left;BSNodeK* _right;K _key;BSNode(K val K()):_left(nullptr), _right(nullptr), _key(val){}}; 接着我们实现插入函数逻辑并不困难总结如下 树为空则直接新增节点赋值给root指针 树不空按二叉搜索树性质查找插入位置插入新节点插入有成功与失败一说假如插入的值已存在于树内则插入失败以K值为判定条件插入左子树或者右子树比K大插右子树比K小插左子树需要额外创建一个父节点来链接节点。//以K值为判定条件插入左子树或者右子树比K大插右子树比K小插左子树//若遇到相等的插入失败不插bool Insert(const K val){if (_root nullptr){_root new Node(val);return true;}Node* cur _root;Node* parent cur;while (cur){//比K小往左子树走if (val cur-_key){parent cur;cur cur-_left;}//比K大往右子树走else if (val cur-_key){parent cur;cur cur-_right;}//相等插入不了返回一个falseelse{return false;}}//跳出while时也就是遇到空了新建一个节点赋值然后链接节点if (parent-_key val)parent-_right new Node(val);else if (parent-_key val)parent-_left new Node(val);return true;} 插入函数实现递归 二叉树的插入也可以是递归毕竟二叉树的结构本身就适合递归
递归的逻辑
终止条件遇到了空那么就是到位了或者说一个空节点,创建节点准备链接本次递归应该做的事检查当前插入的值是否大于K大于走右树小于走左树返回的信息同循环版本返回true Or false但是这里有个问题想要在类内部实现递归轻而易举直接传递根节点即可但是它的访问限定符是私有这意味着我们无法在类外部调用这个递归插入所以我们还需要额外实现一个GetRoot或者是私有的内嵌递归函数来获取到根。 其中传递的形参必须是引用因为递归的栈帧问题要 是想要在递归的途中链接节点之间的指针还需要额外的parent的节点但会让程序变得冗杂一个引用则可以非常巧妙地解决问题因为正好上一层传递下来的引用就是父节点的别名直接链接即可。
同样的借助二级指针也是可以实现的但是完全比不上引用。 bool InsertR(const K val){return _InsertR(_root, val);}private:bool _InsertR(Node* root,const K val){//假如走到了空那么就是到位了或者是一个空树,创建节点准备链接if (root nullptr){root new Node(val);return true;}//大于向右走if (val root-_key)return _InsertR(root-_right, val);else if (val root-_key)return _InsertR(root-_left, val);elsereturn false;} 查找函数实现 查找的逻辑同插入没什么区别也可以实现递归版本在这里就不列出逻辑了。 //查找函数找到了返回true找不到返回falsebool Find(const K val){Node* cur _root;while (cur){//大于就向右边找if (val cur-_key)cur cur-_right;//小于就向左边查找else if (val cur-_key)cur cur-_left;//相等就找着了elsereturn true;}//没找着return false; } 删除函数实现 删除的情况较多且有些复杂逻辑如下 删除有三种情况
删一个有孩子的节点若其左为空把右边给父节点若右边为空则把左边的孩子给父节点 删一个带有多个孩子的节点比较复杂,需要替换删除期间也需要注意删除根的情况,找右子树的最小节点也就是右子树的最左边的节点与被删除的节点交换然后删去右子树最左节点。
情况1,2 示意图 情况3示意图,图中示意为替换法逻辑还需要额外处理删除根节点的情况。 那么代码实现如下 bool erase(const K val){Node* cur _root;Node* parent nullptr;while (cur){if (val cur-_key){parent cur;cur cur-_right;}else if (val cur-_key){parent cur;cur cur-_left;}//相等就找到了找到后进行删除else{//左孩子为空,右孩子为空以及左右都不为空,其中这三种情况下还需要特殊处理删除根节点的时候//其中只有一个孩子的情况下只需要托孤即可if (cur-_left nullptr){//如果左孩子为空那么先判断一下是不是根节点。if (cur _root){//是根节点直接让cur-的右边做根_root cur-_right;}//删的不是根直接托孤给parentelse{//需要被托孤的是到if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;cur nullptr;}//有左孩子没右孩子else if (cur-_right nullptr){//如果是根就把根给到左孩子if (cur _root)_root cur-_left;else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;cur nullptr;}//左右孩子都不是空需要替换删除期间也需要注意删除根的情况else{//找右子树的最小节点也就是右子树的最左边//先找最小值有根判根//留一个parent以防止min后面还有节点Node* minparent cur;Node* min cur-_right;while (min-_left){minparent min;min min-_left;}cur-_key min-_key;//给完跟在删除min之前还要把min后面的节点都街上if (minparent-_left min)minparent-_left min-_right;elseminparent-_right min-_right;delete min;min nullptr;}return true;}}//没找着return false;} 删除函数实现递归 主体逻辑同循环版本差不太多需要注意的是替换法删除的部分可以很巧妙的再次调用一次递归去删除被替换的节点。 bool _earseR(Node* root, const K val){if (root nullptr)return false;if (root-_key val){return _earseR(root-_left, val);}else if(root-_key val){return _earseR(root-_right, val);}else//找到了{//叶子节点无需特殊处理在处理单子树的过程中顺带解决了//没有左孩子,那么一定有右孩子,直接链接右孩子到父节点,这种情况是根节点的完全没有左子树也就是直接更新根//用一个节点保存前根Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else//交换但是走的是递归可以很巧妙的交换两个节点的值然后再走递归去删掉替死鬼。{Node* min root-_right;while (min-_left)min min-_left;swap(root-_key, min-_key);return _earseR(root-_right, val);}delete del;del nullptr;return true;}}Node* _root nullptr;}; 中序遍历实现 这块就没啥好说的除了记得需要额外内嵌一个递归函数。 void InOrder(){Node* root GetRoot();_inorder(root);}void _inorder(Node* _root){if (_root nullptr){return;}_inorder(_root-_left);cout _root-_key ;_inorder(_root-_right);} 拷贝构造函数实现 由于搜索二叉树的插入顺序会对形状产生影响我们使用递归来对其节点挨个拷贝。 //拷贝构造//拷贝构造走一个前序遍历构建走一个递归。每前序遍历一个节点就新建一个节点BSTree(const BSTreeK t2){_root Copy(t2._root);}// 1.终止条件?走到空结束// 2.这次递归应该完成的任务创建节点// 3.返回的信息返回节点的指针空反指针并将节点链接起来//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;} 析构函数实现 //析构函数~BSTree(){Destory();_root nullptr;}//销毁void Destory(){while (_root)erase(_root-_key);}赋值重载 同vector一样我们使用摇人打工法实现赋值重载。 BSTreeK operator (const BSTreeK t){if (t this)return *this;swap(_root, t._root);return *this;}
那么以上就是一个具有最基本功能的搜索二叉树了接下来我们尝试实现一下其KV结构。
KV结构也就是类似于Pair的结构一个Key绑定对应的Val通过对比Key来找到对应的Val。
templateclass K, class Vclass KVTree{public:typedef KVNodeK,V Node;bool Insert(const K key,const V val){if (_root nullptr){_root new Node(key,val);return true;}Node* cur _root;Node* parent cur;while (cur){//比K小往左子树走if (key cur-_key){parent cur;cur cur-_left;}//比K大往右子树走else if (key cur-_key){parent cur;cur cur-_right;}//相等插入不了返回一个falseelse{return false;}}//跳出while时也就是遇到空了新建一个节点赋值然后链接节点if (parent-_key key){parent-_right new Node(key,val);}else if (parent-_key key){parent-_left new Node(key,val);}return true;}Node* 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 cur;}}//没找着return nullptr;}void InOrder(){Node* root GetRoot();_inorder(root);}void _inorder(Node* _root){if (_root nullptr)return;_inorder(_root-_left);cout _root-_key : _root-_valendl;_inorder(_root-_right);}private:Node* GetRoot(){return _root;}Node* _root nullptr;};借助一个统计水果出现的次数来测试一下 void TextKVtree1(){KVTreestring, int KV;string str[] { 菠萝,荔枝,草莓,菠萝,菠萝 ,西瓜 ,草莓 ,橙子 ,荔枝 ,牛油果 ,西瓜 ,西瓜 };for (auto e : str){KVNodestring, int* ret KV.Find(e);if (ret){ret-_val;}else{KV.Insert(e,1);}}KV.InOrder();} 如上就是一个二叉搜索树的基本实现
