当前位置：首页 > news >正文

租网站服务器价格青岛运营网络推广业务

news 2025/7/16 7:39:19

租网站服务器价格,青岛运营网络推广业务,导航网站模板,微信里的商家链接网站怎么做的目录概念性能分析二叉搜索树的插入二叉树的查找二叉树的前序遍历二叉搜索树的删除（重点） 完整代码 key与value的使用概念对于一个二叉搜索树若它的左子树不为空，则左子树上所有的节点的值都小于等于根节点的值若它的右子树不为空…

概念

性能分析

二叉搜索树的插入

二叉树的查找

二叉树的前序遍历

二叉搜索树的删除（重点）

完整代码

key与value的使用

概念

对于一个二叉搜索树

若它的左子树不为空，则左子树上所有的节点的值都小于等于根节点的值
若它的右子树不为空，则右字数上所有的节点的值都大于等于根节点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景

template<class K,class V>
struct BSTreeNode
{typedef BSTreeNode<K, V> Node;BSTreeNode(const K& key,const V& val):_key(key),_value(val){}K _key;V _value;Node* _left = nullptr;Node* _right = nullptr;
};

性能分析

指出二叉搜索树：

最优情况下，二叉搜索树近似为完全二叉树，高度为 $\log_{2} N$
最差情况下，二叉搜索树退化为类似于单支树，高度为 $N$
最优情况下增删查改为 $O\left ( log_{2}N\right )$
最差情况下增删查改为 $O\left ( {N} \right )$
综合来讲时间复杂度为 $O\left ( N \right )$

指出二分查找：

二分查找需要在允许下标随机访问的结构中
二分查找需要在有序的结构中
二分查找的时间复杂度为 $O\left ( log_{2}N \right )$
二分查找对应的结构一般为数组，它挪动数据的时间复杂

二叉搜索树的插入

树为空，直接增新节点，赋值给root指针
树不为空，按照性质，插入值比当前节点大走右边，反之走左边，插入空位置
如果支持插入相等的值可以插左边或者右边（但是插左边就都插左边，反之相同）

int num[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

bool Insert(const K& key, const V& value)
{if (_root == nullptr){_root = new Node(key, value);return true;}else{bool right = true;Node* p = _root;Node* c = _root;while (c != nullptr){p = c;if (key > c->_key){right = true;c = p->_right;}else if(key < c->_key){right = false;c = p->_left;}else{return false;}}c = new Node(key, value);if (right){p->_right = c;}else{p->_left = c;}return true;}
}

二叉树的查找

从根开始查找，key比节点大就走右，比节点小就走左边
最多查找高度次数，走到空还没找到就不存在
不支持插入相等的值，找到x就返回，反之继续查找直到高度次

	Node* Find(const K& key,Node** p = nullptr){	Node* ptr = _root;while (ptr){if (key > ptr->_key){if (p)*p = ptr;ptr = ptr->_right;}else if (key < ptr->_key){if (p)*p = ptr;ptr = ptr->_left;}elsereturn ptr;}return ptr;}

二叉树的前序遍历

采用递归
打印左边节点
打印中间节点
打印右边节点

	void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << '{' << root->_value << '}' << ' ';_InOrder(root->_right);}

二叉搜索树的删除（重点）

先查找是否存在，不存在返回false
若存在有以下四种情况
删除节点的左右孩子均为空
直接删除然后给空

删除节点的左（右）孩子为空，另一边不为空
把节点的父亲对应的孩子节点的指针指向孩子不为空的一边，然后删除节点

删除节点左右均不为空
找左子树的最大节点（右子树的最小节点）替代删除节点，，然后删除最值节点

bool Erase(const K& key)
{Node* par = _root;Node* ptr = Find(key,&par);if (!ptr)return false;if (ptr == par){delete ptr;_root = nullptr;return true;}if(!ptr->_left&&!ptr->_right){if(par->_left == ptr)par->_left = nullptr;if(par->_right == ptr)par->_right = nullptr;delete ptr;return true;}else if (!ptr->_left && ptr->_right)//左空右不空{if (par->_left == ptr){par->_left = ptr->_right;}if (par->_right == ptr){par->_right = ptr->_right;}delete ptr;return true;}else if(ptr->_left && !ptr->_right){if (par->_left == ptr){par->_left = ptr->_left;}if (par->_right == ptr){par->_right = ptr->_left;}delete ptr;return true;}else//两边均不为空直接替换操作{//找左侧最大节点Node* Max = ptr->_left;Node* Maxp = ptr;while (Max->_right != nullptr){Maxp = Max;Max = Max->_right;}//交换ptr->_key = Max->_key;ptr->_value = Max->_value;//删除MAX的位置if (Maxp == ptr){ptr->_left = Max->_left;}else if (Max->_left){Maxp->_right = Max->_left;}else{Maxp->_right = Max->_right;}//删除Maxdelete Max;return true;}return false;
}

完整代码

#pragma once
#include<iostream>
#include<string>
using namespace std;template<class K,class V>
struct BSTreeNode
{
public:typedef BSTreeNode<K, V> Node;BSTreeNode(const K& key,const V& val):_key(key),_value(val){}K _key;V _value;Node* _left = nullptr;Node* _right = nullptr;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:bool Insert(const K& key, const V& value) {if (_root == nullptr) {_root = new Node(key, value);return true;}else {bool right = true;Node* p = _root;Node* c = _root;while (c != nullptr) {p = c;if (key > c->_key) {right = true;c = p->_right;}else if (key < c->_key){right = false;c = p->_left;}else{return false;}}c = new Node(key, value);if (right){p->_right = c;}else{p->_left = c;}return true;}}Node* Find(const K& key,Node** p = nullptr){	Node* ptr = _root;while (ptr){if (key > ptr->_key){if (p)*p = ptr;ptr = ptr->_right;}else if (key < ptr->_key){if (p)*p = ptr;ptr = ptr->_left;}elsereturn ptr;}return ptr;}bool Erase(const K& key){Node* par = _root;Node* ptr = Find(key,&par);if (!ptr)return false;if (ptr == par){delete ptr;_root = nullptr;return true;}if(!ptr->_left&&!ptr->_right){if(par->_left == ptr)par->_left = nullptr;if(par->_right == ptr)par->_right = nullptr;delete ptr;return true;}else if (!ptr->_left && ptr->_right)//左空右不空{if (par->_left == ptr){par->_left = ptr->_right;}if (par->_right == ptr){par->_right = ptr->_right;}delete ptr;return true;}else if(ptr->_left && !ptr->_right){if (par->_left == ptr){par->_left = ptr->_left;}if (par->_right == ptr){par->_right = ptr->_left;}delete ptr;return true;}else//两边均不为空直接替换操作{//找左侧最大节点Node* Max = ptr->_left;Node* Maxp = ptr;while (Max->_right != nullptr){Maxp = Max;Max = Max->_right;}//交换ptr->_key = Max->_key;ptr->_value = Max->_value;//删除MAX的位置if (Maxp == ptr){ptr->_left = Max->_left;}else if (Max->_left){Maxp->_right = Max->_left;}else{Maxp->_right = Max->_right;}//删除Maxdelete Max;return true;}return false;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << '{' << root->_value << '}' << ' ';_InOrder(root->_right);}Node* _root = nullptr;
};

key与value的使用

void TestBSTree()
{BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}}//string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };统计水果出现的次//BSTree<string, int> countTree;//for (auto str : strs)//{//	auto ret = countTree.Find(str);//	if (ret == NULL)//	{//		countTree.Insert(str, 1);//	}//	else//	{//		ret->_value++;//	}//}//countTree.InOrder();
}