#pragma once
#include
using namespace std;
template
struct BsTreeNode{//二叉树 节点
K _key;
V _value;
BsTreeNode* _left;
BsTreeNode* _right;
BsTreeNode(const K& key,const V& value)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
{}
};
template
class BsTree{
public:
typedef BsTreeNode Node;
BsTree()
: _root(NULL)
{
}
~BsTree(){}
bool Insert(const K& key, const V& value)//插入 非递归
{
if (_root == NULL){
_root = new Node(key, value);
return true;
}
Node* cur = _root;
while (1){
if (cur->_key > key)
{
if (cur->_left)
cur = cur->_left;
else{
cur->_left = new Node(key, value);
return true;
}
}
else if (cur->_key < key)
{
if (cur->_right)
cur = cur->_right;
else{
cur->_right = new Node(key, value);
return true;
}
}//以上为找 插入位置 并插入
else if (cur->_key == key)//存在 插入失败
return false;
}
}
bool InsertR(const K& key,const V& value)//插入 递归
{
return _InsertR(_root,key,value);
}
Node* Find(const K& 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 NULL;
}
bool RemoveR(const K& key)//删除 递归
{
if (_root == NULL)
return false;
return _RemoveR(_root,key);
}
bool Remove(K key){//删除 非递归
Node* cur=_root, *prev=NULL;
while (cur){
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
prev = cur;
cur = cur->_right;
}// 以上为 找到要删除的 节点
else
{
if (cur->_left == NULL)//如果节点左或右为空，直接删除该节//点将之后的节点 连接在其父节点
{
if (prev == NULL)
{
_root = cur->_right;
}
else if (prev->_left == cur)
{
prev->_left = cur->_right;
}
else
prev->_right = cur->_right;
}
else if (cur->_right == NULL)//同上 右为空
{
if (prev == NULL)
{
_root = cur->_left;
delete cur;
}
else if (prev->_right == cur)
{
prev->_right = cur->_left;
}
else
prev->_left = cur->_left;
}
else//如果左右都不为空 找右孩子最左 或 左孩子最右 节点替
//代删除
{
prev = cur;
cur = cur->_right;
while (cur->_left){
cur = cur->_left;
}
prev->_key = cur->_key;
prev->_value = cur->_value;
prev->_right =cur->_right;
}
delete cur;
return true;
}
}
return false;
}
bool modification(K key,V value){//修改
Node* ret = Find(key);
if (ret == NULL)
return false;
ret->_value = value;
return true;
}
private:
bool _InsertR(Node* & root,const K& key,const V& value)//插入 递归函数
{
if (root == NULL)
{
root = new Node(key,value);
return true;
}
if (root->_key == key)
return false;
else if (root->_key > key)
return _InsertR(root->_left,key,value);
else
return _InsertR(root->_right,key,value);
}
bool _RemoveR(Node* & root,const K& key)//删除 递归函数
{
if (root->_key < key)
return _RemoveR(root->_right, key);
if (root->_key>key)
return _RemoveR(root->_left, key);
if (root->_left == NULL)
{
Node* dev = root;
root = root->_right;
delete dev;
return true;
}
else if (root->_right == NULL)
{
Node* dev = root;
root = root->_left;
delete dev;
return true;
}
else
{
root->_key = root->_right->_key;
root->_value = root->_right->_value;
return _RemoveR(root->_right,root->_key);
}
}
Node* _root;
};
网页名称：c++搜索二叉树/排序二叉树
标题链接：
http://shouzuofang.com/article/jjchcp.html