二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
创新互联公司服务项目包括玉屏网站建设、玉屏网站制作、玉屏网页制作以及玉屏网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，玉屏网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到玉屏省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
1、每一个节点都有一个作为搜索依据的关键码，所有节点的关键码互不相同。
2、左子树上所有节点的关键码都小于跟节点的关键码。
3、右子树上所有节点的关键码都大于跟节点的关键码。
4、左右子树都是二叉树搜索树。
#include
using namespace std;
template
struct TreeNode
{
T Data;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
TreeNode(T data)
:left(NULL)
,right(NULL)
,Data(data)
,parent(NULL)
{}
};
template
class BStree
{
public:
BStree()
{}
~BStree()
{}
BStree(T *arr,size_t sz);
void Insert(T data)
{
TreeNode *tmp = new TreeNode(data);
InsertBStree(_root,tmp);
}
void Search(T data)
{
TreeNode *tmp = new TreeNode(data);
tmp = SearchBStree(_root,tmp);
if(tmp)
cout<<'Y'<* node = MinBStree(_root);
cout<Data<* node = MaxBStree(_root);
cout<Data<* node = MaxLeftBStree(_root);
cout<Data<* node = MinRightBStree(_root);
cout<Data< *tmp = new TreeNode(data);
tmp = SearchBStree(_root,tmp);
if (tmp)
tmp = prevBStree(tmp);
cout<Data< *tmp = new TreeNode(data);
tmp = SearchBStree(_root,tmp);
if (tmp)
tmp = postBStree(tmp);
cout<Data< *tmp = new TreeNode(data);
tmp = SearchBStree(_root,tmp);
if (tmp)
DeleteBStree(tmp);
}
void Destroy()
{
DestroyBStree(_root);
}
void Mid()
{
MidOrder(_root);
}
void MidOrder(TreeNode *Root)
{
if(Root==NULL)
return;
MidOrder(Root->left);
cout<Data<<" ";
MidOrder(Root->right);
}
protected:
void InsertBStree(TreeNode *root,TreeNode *Node);
TreeNode* SearchBStree(TreeNode *Root,TreeNode *Node);
TreeNode* MinBStree(TreeNode* Root);
TreeNode* MaxBStree(TreeNode* Root);
TreeNode* MaxLeftBStree(TreeNode *Root);
TreeNode* MinRightBStree(TreeNode *Root);
TreeNode* prevBStree(TreeNode *Node);
TreeNode* postBStree(TreeNode *Node);
void DeleteBStree(TreeNode *Node);
void DestroyBStree(TreeNode *Root);
private:
TreeNode * _root;
};
template
BStree::BStree(T *arr,size_t sz)
{
_root = new TreeNode(arr[0]);
for (int i = 1; i < sz; i++)
{
TreeNode *tmp = new TreeNode(arr[i]);
InsertBStree(_root,tmp);
}
}
template
void BStree::InsertBStree(TreeNode *root,TreeNode *Node)
{
if(root==NULL)
root=Node;
else
{
TreeNode *cur=NULL;
while(root)
{
cur=root;
if(root->Data > Node->Data)
{
root=root->left;
}
else
{
root=root->right;
}
}
if(Node->Data > cur->Data)
{
cur->right=Node;
Node->parent = cur;
}
else
{
cur->left=Node;
Node->parent = cur;
}
}
}
template
TreeNode* BStree::SearchBStree(TreeNode* Root,TreeNode *Node)
{
TreeNode *cur=Root;
while(cur&&cur->Data!=Node->Data)
{
if(cur->Data>Node->Data)
{
cur=cur->left;
}
else
{
cur=cur->right;
}
}
if(cur)
return cur;
else
return NULL;
}
template
TreeNode* BStree::MinBStree(TreeNode* Root)
{
TreeNode* cur=Root;
while(cur->left)
{
cur=cur->left;
}
return cur;
}
template
TreeNode* BStree::MaxBStree(TreeNode* Root)
{
TreeNode* cur=Root;
while(cur->right)
{
cur=cur->right;
}
return cur;
}
template
TreeNode* BStree::MaxLeftBStree(TreeNode *Root)
{
if (Root->left == NULL)
return NULL;
TreeNode* cur = Root->left;
while(cur->right)
{
cur = cur->right;
}
return cur;
}
template
TreeNode* BStree::MinRightBStree(TreeNode *Root)
{
if (Root->right == NULL)
return NULL;
TreeNode* cur = Root->right;
while(cur->left)
{
cur = cur->left;
}
return cur;
}
template
TreeNode* BStree::prevBStree(TreeNode *Node)
{
if (Node->left)
return MaxLeftBStree(Node);
TreeNode *P = Node->parent;
if (Node->left == NULL && Node == P->right)
{
return Node->parent;
}
while (P && Node == P->left)
{
Node = P;
P = P->parent;
}
return P;
}
template
TreeNode* BStree::postBStree(TreeNode *Node)
{
if (Node->right)
return MinRightBStree(Node);
TreeNode *P = Node->parent;
if (Node->right == NULL && Node == P->left)
{
return Node->parent;
}
while (P && Node == P->right)
{
Node = P;
P = P->parent;
}
return P;
}
template
void BStree::DeleteBStree(TreeNode *Node)
{
TreeNode *cur = Node->parent;
if (Node->left == NULL && Node->right == NULL)
{
if(Node == cur->left)
{
delete Node;
cur->left = NULL;
}
else
{
delete Node;
cur->right = NULL;
}
}
else if(Node->left == NULL && Node->right)
{
TreeNode *child = Node->right;
if(Node == cur->left)
{
delete Node;
cur->left = child;
}
else
{
delete Node;
cur->right = child;
}
}
else if(Node->right == NULL && Node->left)
{
TreeNode *child = Node->left;
if(Node == cur->left)
{
delete Node;
cur->left = child;
}
else
{
delete Node;
cur->right = child;
}
}
else
{
TreeNode *tmp = postBStree(Node);
Node->Data = tmp->Data;
DeleteBStree(tmp);
}
}
template
void BStree::DestroyBStree(TreeNode *Root)
{
if(Root==NULL)
return;
if(Root->left)
DestroyBStree(Root->left);
if(Root->right)
DestroyBStree(Root->right);
delete Root;
Root = NULL;
}
void Test()
{
int arr[] = {5,3,4,1,7,8,2,6,0,9};
int sz = sizeof(arr)/sizeof(arr[0]);
BStree BS(arr,sz);
/*BS.Mid();
BS.Insert(10);
BS.Mid();*/
/*BS.Max();
BS.Min();
BS.MaxLeft();
BS.MinRight();
BS.Search(6);*/
//BS.PrevNode(9);
//BS.PostNode(4);
BS.DeleteNode(5);
BS.Mid();
//BS.Destroy();
//BS.Mid();
}
int main()
{
Test();
return 0;
}
本文题目：二叉搜索树
当前地址：
http://bjjierui.cn/article/gjchhp.html
