插入
插入节点每一次都是插在叶子节点
实现起来比较简单
实现了递归与非递归
bool _InsertR(Node* root,const K& key)
{
//初始化插入结点
Node* node=new Node(key);
node->_key=key;
node->_left=node->_right=node->_parent=NULL;
//空树时，直接作为根结点
if((root)==NULL)
{
root=node;
return true;
}
//插入到当前结点（*root）的左孩子
if((root)->_left == NULL && (root)->_key > key){
node->_parent=root;
root->_left=node;
return true;
}
//插入到当前结点（*root）的右孩子
if((root)->_right == NULL && (root)->_key < key){
node->_parent=root;
(root)->_right=node;
return true;
}
if(root->_key > key)
_InsertR(root->_left,key);
else if(root->_key < key)
_InsertR(root->_right,key);
else
return true;
｝
bool _Insert2(Node*& root,const K& key)
{
if(root==NULL)
{
root=new Node(key);
return true;
}
if(root->_key<key)
return _Insert2(root->_right,key);
else if(root->_key>key)
return _Insert2(root->_left,key);
else
return false;
}查找
bool FindR(const K& key)
{
if(_root==NULL)
return false;
Node* cur=_root;
while(cur)
{
if(cur->_key<key)
cur=cur->_right;
else if(cur->_key>key)
cur=cur->_left;
else
return true;
}
}
删除节点比较难，分四种情况
1.被删节点无左孩子
2.被删节点无右孩子
3.被删节点无左孩子也无右孩子
4.被删节点既有右孩子又有左孩子
递归实现
bool _Remove(Node*& root,const K& key)
{
if (root==NULL)
{
return false;
}
if(root->_key<key)
{
return _Remove(root->_right,key);
}
else if(root->_key>key)
{
return _Remove(root->_left,key);
}
else
{
Node* del=root;
if(root->_left==NULL)
{
root=root->_right;
}
else if(root->_right==NULL)
{
root=root->_left;
}
delete del;
}
return true;
}非递归实现
bool Remove(const K& key)//非递归
{
if(_root==NULL)
return false;
Node* pre=NULL;
Node* cur=_root;
Node* del=cur;
while (cur&&cur->_key!=key)
{
if(cur->_key>key)
{
pre=cur;
cur=cur->_left;
}
else if (cur->_key<key)
{
pre=cur;
cur=cur->_right;
}
}
if(cur->_left==NULL)
{
if(cur==_root)
_root=cur->_right;
else if(cur==pre->_left)
{
pre->_left=cur->_right;
}
else
{
pre->_right=cur->_right;
}
del=cur;
}
else if (cur->_right==NULL)
{
if(cur==_root)
{
_root=cur->_left;
}
else if (pre->_left==cur)
{
pre->_left==cur->_left;
}
else
{
pre->_right=cur->_left;
}
del=cur;
}
else
{
Node* minRight=cur->_right;//右孩子最左节点
pre=cur;
while (minRight->_left)
{
pre=minRight;
minRight=minRight->_left;
}
del=minRight;
cur->_key=minRight->_key;//交换节点值
if(pre->_left==minRight)
{
pre->_left=minRight->_right;
}
else
{
pre->_right=minRight->_right;
}
}
delete del;
return true;
}
源代码
#include<iostream>
using namespace std;
template<class K>
struct SearchBinaryTreeNode
{
SearchBinaryTreeNode<K>* _left;
SearchBinaryTreeNode<K>* _right;
SearchBinaryTreeNode<K>* _parent;
K _key;
SearchBinaryTreeNode(const K& key)
:_key(key),_left(NULL),_right(NULL),_parent(NULL)
{}
};
template<class K>
class SearchBinaryTree
{
typedef SearchBinaryTreeNode<K> Node;
public:
SearchBinaryTree()
:_root(NULL)
{}
SearchBinaryTree(const SearchBinaryTree<K>& t)
{
_root=t->_root;
}
~SearchBinaryTree()
{
delete _root;
}
bool InsertR(const K& key) // 插入节点
{
if (!_root) // 空树
{
_root = new Node(key);
_root->_key = key;
}
else
{
_InsertR(_root,key);
}
return true;
}
bool Insert2(const K& key)//递归
{
_Insert2(_root,key);
return true;
}
bool Remove2(const K& key)//递归
{
_Remove(_root,key);
return true;
}
bool Remove(const K& key)//非递归
{
if(_root==NULL)
return false;
Node* pre=NULL;
Node* cur=_root;
Node* del=cur;
while (cur&&cur->_key!=key)
{
if(cur->_key>key)
{
pre=cur;
cur=cur->_left;
}
else if (cur->_key<key)
{
pre=cur;
cur=cur->_right;
}
}
if(cur->_left==NULL)
{
if(cur==_root)
_root=cur->_right;
else if(cur==pre->_left)
{
pre->_left=cur->_right;
}
else
{
pre->_right=cur->_right;
}
del=cur;
}
else if (cur->_right==NULL)
{
if(cur==_root)
{
_root=cur->_left;
}
else if (pre->_left==cur)
{
pre->_left==cur->_left;
}
else
{
pre->_right=cur->_left;
}
del=cur;
}
else
{
Node* minRight=cur->_right;//右孩子最左节点
pre=cur;
while (minRight->_left)
{
pre=minRight;
minRight=minRight->_left;
}
del=minRight;
cur->_key=minRight->_key;//交换节点值
if(pre->_left==minRight)
{
pre->_left=minRight->_right;
}
else
{
pre->_right=minRight->_right;
}
}
delete del;
return true;
}
bool FindR(const K& key)
{
if(_root==NULL)
return false;
Node* cur=_root;
while(cur)
{
if(cur->_key<key)
cur=cur->_right;
else if(cur->_key>key)
cur=cur->_left;
else
return true;
}
}
void InOrder()//中序遍历
{
_InOrder(_root);
cout<<endl;
}
protected:
bool _InsertR(Node* root,key);
else
return true;
}
bool _Insert2(Node*& root,key);
else
return false;
}
void _InOrder(Node* root)
{
Node* cur=root;
if(cur==NULL)
return;
_InOrder(cur->_left);
cout<<cur->_key<<" ";
_InOrder(cur->_right);
}
bool _Remove(Node*& root,key);
}
else
{
Node* del=root;
if(root->_left==NULL)
{
root=root->_right;
}
else if(root->_right==NULL)
{
root=root->_left;
}
delete del;
}
return true;
}
private:
Node* _root;
};
void test()
{
SearchBinaryTree<int> BSTree;//15,6,18,3,7,17,20,2,4,13,9
BSTree.InsertR(15);
BSTree.InsertR(6);
BSTree.InsertR(18);
BSTree.InsertR(3);
BSTree.InsertR(7);
BSTree.InsertR(17);
BSTree.InsertR(20);
BSTree.InsertR(2);
BSTree.InsertR(4);
BSTree.InsertR(13);
BSTree.InsertR(9);
BSTree.Insert2(10);
BSTree.InOrder();
BSTree.Remove2(13);
BSTree.InOrder();
BSTree.Remove(6);
BSTree.InOrder();
cout<<BSTree.FindR(2)<<endl;
cout<<BSTree.FindR(20)<<endl;
BSTree.InOrder();
}
原文链接：https://www.f2er.com/datastructure/382424.html