<span style="font-family: Arial,Helvetica,sans-serif; background-color: rgb(255,255,255);">二叉搜索树的意思就是在这个二叉树中每一个左孩子的值都比他的父节点小，每一个右孩子的值都比父节点的大，中序遍历后会出现一个有序的数组</span>
插入
插入节点每一次都是插在叶子节点
实现起来比较简单
实现了递归与非递归
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