二叉排序树又叫二叉查找树。
遵循三个原则：
1、一棵树要么为空，要么
2、左孩子节点小于根节点值，根节点值小于右孩子节点值
3、子树也具备这个规则
代码：
#include <iostream>
#include <cstdlib>
using namespace std;
static int flag=0;
typedef struct binst
{
int data;
struct binst *lchild;
struct binst *rchild;
}*BST;
void createBST(BST &bst,int key)
{
BST t,p,pre;
t=(BST)malloc(sizeof(struct binst));
if(!t)
{
cout<<"allocate fail";
return;
}
t->data=key;
t->lchild=NULL;
t->rchild=NULL;
if(bst==NULL)
{
bst=t;
}
else
{
p=bst;
while(p)
{
if(p->data==key)
{
free(t);
return;
}
else if(p->data<key)
{
pre=p;
p=p->rchild;
}
else
{
pre=p;
p=p->lchild;
}
}
if(pre->data<key)
{
pre->rchild=t;
}
else
{
pre->lchild=t;
}
}
}
void bstSearch(BST bst,int key)
{
if(bst)
{
if(bst->data==key)
{
flag=1;
cout<<"search success!"<<endl;
return;
}
else if(bst->data<key)
{
bstSearch(bst->rchild,key);
}
else
{
bstSearch(bst->lchild,key);
}
}
if(flag==0)
{
cout<<"search fail!"<<endl;
}
}
void preOrderSearch(BST bst)
{
if(bst)
{
cout<<bst->data<<" ";
preOrderSearch(bst->lchild);
preOrderSearch(bst->rchild);
}
}
int main()
{
BST bst=NULL;
int arr[]={12,3,5,17,15,19,20};
int key;
cout<<"create the BST"<<endl;
for(int i=0;i<7;i++)
{
createBST(bst,arr[i]);
}
cout<<"output the bst:"<<endl;
preOrderSearch(bst);
cout<<endl;
cout<<"please input the key:";
cin>>key;
bstSearch(bst,key);
cout<<endl;
return 0;
}
运行截图：
