目录
成都创新互联专注于马尾网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供马尾营销型网站建设,马尾网站制作、马尾网页设计、马尾网站官网定制、小程序制作服务,打造马尾网络公司原创品牌,更为您提供马尾网站排名全网营销落地服务。二叉搜索树
二叉搜索树实现
非递归插入|非递归查找
删除
推导阶段
非递归删除代码
递归查找
递归插入
递归删除
析构函数
拷贝构造
赋值重载
完整代码
二叉搜索树的应用
Key/Value模型
二叉搜索树实现 非递归插入|非递归查找二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
删除 推导阶段#include
using namespace std; template class BStreeNode { public: BStreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {} BStreeNode * _left; BStreeNode * _right; K _key; }; template class BStree { typedef BStreeNode Node; public: 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; } } cur = new Node(key); if (parent->_key< key) { parent->_right = cur; } else { parent->_left = cur; } return true; } bool Find(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 true; } } return true; } void InOrder() { _InOrder(_root); } private: void _InOrder(Node *root) { if (root == nullptr) return; _InOrder(root->_left); cout<< root->_key<< " "; _InOrder(root->_right); } private: Node* _root = nullptr; }; int main() { BStree t; int a[] = { 1,1,2,2,3,6,165,132,4185,123 }; for (auto e : a) { t.Insert(e); } t.InOrder(); return 0; } 可去重
非递归删除代码1.若要删除的节点是叶子节点,直接删除即可
2.删除节点只有一个孩子
若左为空,则让父亲节点指向该节点的右子树以删除3为例
若果要删除跟节点,而且左为空,若要删除8,我们更新根节点即可,让根节点指向10
若右为空,则让父亲指向左子树,以删除14为例
若果要删除跟节点,而且右为空,若要删除8,让根节点指向3即可
3.要删除的节点其左右节点都不为空
我们可以采用替换法删除节点
用左子树的大节1点或右子树的最小节点4,若采用右树的最小节点,交换3和4删除4之后,删除3,但还有一个子节点5,我们让5成为6的左节点
若要删除8,这里采用右树最左节点的替换法,右树的最左节点就是10自己,如果这样写会有错误,while循环都不会进去,minparent就是空,而后面minParent->_left = min->_right;这个语句会出错,修正方法,让minparent一开始就是cur,并且加个判断。
这样写即可
bool Erase(const K& key)//删除
{
//若有一个子节点,删除父节点后,让子节点填充
//若有俩个子节点,父节点删除后
//1.用左子树的大节点替换父节点
//2.或右子树的最小节点替换父节点
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;
cur = nullptr;
}
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;
cur = nullptr;
}
else//左右都为空,叶子节点,这里采用用右树的最小节点进行删除
{
Node* minParent = cur;
Node*min = cur->_right;//cur是要删除的节点
while (min->_left)//寻找最小节点
{
minParent = min;
min = min->_left;
}
swap(cur->_key, min->_key);
if (minParent->_left == min)
{
minParent->_left = min->_right;
}
else
minParent->_right = min->_right;
delete min;
}
return true;
}
}
return false;
}
递归查找 bool _FindR(Node *root,const K& key)
{
if (root == nullptr)
return false;
if (root->_key< key)
{
return _FindR(root->right, key);
}
else if (root->_key >key)
{
return _FindR(root->left, key);
}
else
{
return true;
}
}
递归插入递归删除这种插入写法会导致二叉树断开
这里的Node没有跟父节点连接上,而是创建了一个空间单独在那里
加上引用即可
bool _InsertR(Node*& root, const K& key) { if (root == nullptr)//根为空,直接插入 { root = new Node(key); return true; } if (root->_key< key) { return _InsertR(root->_right, key); } else if (root->_key >key) { return _InsertR(root->_left, key); } else { return false; } }
析构函数bool _Eraser(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key< key) { return _Eraser(root->_right, key); } else if (root->_key >key) { return _Eraser(root->_left, key); } 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 _Eraser(root->_right, key); } delete del; return true; } }
~BStree()
{
Destory(_root);
}
private:
void Destory(Node*& root)//采用引用可让root置空起作用
{
if (root ==nullptr)
return;
Destory(root->_left);
Destory(root->right);
delete root;
root=nullptr
}
拷贝构造 赋值重载注:拷贝构造也是构造,如果写了构造,编译器不会生成默认构造,会报错没有合适的默认构造
BStree(const BStree
& t) { _root = _Copy(t._root); } Node* _Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* copyRoot = new Node(root->_key); copyRoot->_left = _Copy(root->_left); copyRoot->_right = _Copy(root->_right); return copyRoot; } 我们需加默认构造
默认构造也可写为BSTree()=default;
这是强制编译器生成默认构造,是C++11的用法
BStree
& operator=(BStree t) { swap(_root, t._root); return *this; }
完整代码搜索二叉树增删查的时间复杂度是:O(h),h代表高度
#includeusing namespace std;
templateclass BStreeNode
{
public:
BStreeNode(const K& key)
:_left(nullptr),
_right(nullptr),
_key(key)
{}
BStreeNode* _left;
BStreeNode* _right;
K _key;
};
templateclass BStree
{
typedef BStreeNodeNode;
public:
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;
}
}
cur = new Node(key);
if (parent->_key< key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
void InOrder()//排序
{
_InOrder(_root);
}
bool Find(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 true;
}
}
return true;
}
bool Erase(const K& key)//删除
{
//若有一个子节点,删除父节点后,让子节点填充
//若有俩个子节点,父节点删除后
//1.用左子树的大节点替换父节点
//2.或右子树的最小节点替换父节点
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;
cur = nullptr;
}
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;
cur = nullptr;
}
else//左右都为空,叶子节点,这里采用用右树的最小节点进行删除
{
Node* minParent = cur;
Node* min = cur->_right;//cur是要删除的节点
while (min->_left)//寻找最小节点
{
minParent = min;
min = min->_left;
}
swap(cur->_key, min->_key);
if (minParent->_left == min)
{
minParent->_left = min->_right;
}
else
minParent->_right = min->_right;
delete min;
}
return true;
}
}
return false;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _Eraser(_root, key);
}
~BStree()
{
Destory(_root);
}
BStree()
{}
BStree(const BStree& t)
{
_root = _Copy(t._root);
}
BStree& operator=(BStreet)
{
swap(_root, t._root);
return *this;
}
private:
Node* _Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyRoot = new Node(root->_key);
copyRoot->_left = _Copy(root->_left);
copyRoot->_right = _Copy(root->_right);
return copyRoot;
}
void Destory(Node*& root)//采用引用可让root置空起作用
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
bool _Eraser(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key< key)
{
return _Eraser(root->_right, key);
}
else if (root->_key >key)
{
return _Eraser(root->_left, key);
}
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 _Eraser(root->_right, key);
}
delete del;
return true;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)//根为空,直接插入
{
root = new Node(key);
return true;
}
if (root->_key< key)
{
return _InsertR(root->_right, key);
}
else if (root->_key >key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node *root,const K& key)
{
if (root == nullptr)
return false;
if (root->_key< key)
{
return _FindR(root->right, key);
}
else if (root->_key >key)
{
return _FindR(root->left, key);
}
else
{
return true;
}
}
void _InOrder(Node *root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_key<< " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
int main()
{
BStreet;
int a[] = { 1,1,2,2,3,6,165,132,4185,123 };
for (auto e : a)
{
t.Insert(e);
}
BStreecopy = t;
copy.InOrder();
t.InOrder();
BStreet1;
t1.Insert(2);
t1.Insert(1);
t1.Insert(3);
copy = t1;
copy.InOrder();
cout<< endl;
t1.InOrder();
cout<< endl;
return 0;
}
二叉搜索树的应用Key/Value模型.K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到
的值。
比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误
KV模型:每一个关键码key,都有与之对应的值Value,即
的键值对。该种方
式在现实生活中非常常见:
比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
文单词与其对应的中文就构成一种键值对; 再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
现次数就是就构成一种键值对
KV模型通过K去找V
namespace KeyValue
{
templatestruct BSTreeNode
{
BSTreeNode* _left;//Key和Value绑到一起
BSTreeNode* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
templateclass BSTree
{
typedef BSTreeNodeNode;
public:
bool Insert(const K& 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->_right;
}
else if (cur->_key >key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key< key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)//查找的时候以K去查找,返回的时候返回节点指针,以便于修改
{
Node* cur = _root;
while (cur)
{
if (cur->_key< key)
{
cur = cur->_right;
}
else if (cur->_key >key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)//用K删除
{
//...
return true;
}
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);
}
private:
Node* _root = nullptr;
};
英译汉
统计水果出现的次数
链表相交和复杂链表的赋值可用kv模型。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧