#include
using namespace std;
template
struct BiNode{
DataType data;
BiNode *lchild;
BiNode *rchild;
};
template
class BiSortTree
{
public:
BiSortTree(DataType a[],int n);
~BiSortTree(){
DestoryBiSortTree(root);
}
void InsertBST(BiNode *s){
InsertBST(root,s);
}
void DeleteBST(BiNode *f){
DeleteBST(root,f);
}
BiNode *SearchBST(DataType k){
return SearchBST(root,k);
}
void Levershow();
void Inshow(){
Inshow(root);
}
void Preshow(){
Preshow(root);
}
private:
BiNode *root;
void DestoryBiSortTree(BiNode *bt);
void Preshow(BiNode *root);
void Inshow(BiNode *root);
void InsertBST(BiNode *root,BiNode *s);
void DeleteBST(BiNode *p,BiNode *f);
BiNode *SearchBST(BiNode *root,DataType k);
} ;
template
void BiSortTree::InsertBST(BiNode *root,BiNode *s)
{
if(root==NULL) root=s;
else if(root->data>s->data)
InsertBST(root->lchild,s);
else
InsertBST(root->rchild,s);
}
template
BiSortTree::BiSortTree(DataType a[],int n)
{
//root=new BiNode;
root=NULL;
BiNode *s;
for(int i=0;i
s=new BiNode;
s->data=a[i];
s->lchild=NULL;
s->rchild=NULL;
InsertBST(root,s);
}
cout<<"完成构造函数" <
}
template
void BiSortTree::DeleteBST(BiNode *p,BiNode *f)
{
if((p->lchild==NULL)&&(p->rchild==NULL)){
f->lchild=NULL;
delete p;
}else if(p->rchild==NULL){
f->lchild=p->lchild;
delete p;
}else if(p->rchild==NULL){
f->lchild=p->rchild;
delete p;
}else{
BiNode *parent,*s;
parent=p;
s=p->rchild;
while(s->lchild!=NULL){
parent=s;
s=s->lchild;
}
p->data=s->data;
if(parent==p) parent->rchild=s->rchild;
else parent->lchild=s->rchild;
delete s;
}
}
template
void BiSortTree::DestoryBiSortTree(BiNode *bt)
{
if(bt!=NULL){
DestoryBiSortTree(bt->lchild);
DestoryBiSortTree(bt->rchild);
delete bt;
}
}
template
BiNode *BiSortTree::SearchBST(BiNode *root,DataType k)
{
if(root==NULL) return NULL;
else if(root->data==k) return root;
else if(root->datarchild,k);
else return SearchBST(root->lchild,k);
}
template
void BiSortTree::Levershow(){
cout<<"采用了层序遍历"<
BiNode *Q[1000];
int rear=-1,front=-1;
if(root==NULL) return;
Q[++rear]=root;
BiNode *T;
while(rear!=front){
T=Q[++front];
cout<data<<" ";
if(T->lchild!=NULL) Q[++rear]=T->lchild;
if(T->rchild!=NULL) Q[++rear]=T->rchild;
}
}
template
void BiSortTree::Preshow(BiNode *root)
{
cout<<"采用前序非递归算法:";
BiNode *Q[1000];
int top=-1;
if(root==NULL) return;
Q[++top]=root;
while(top!=-1&&root!=NULL)
{
BiNode *T;
while(root!=NULL)
{
T=Q[--top];
cout<data<<" ";
root=root->lchild;
}
if(top!=-1){
root=Q[--top];
root=root->rchild;
}
}
}
template
void BiSortTree::Inshow(BiNode *root)
{
cout<<"采用中序递归算法"<
if(root==NULL) return;
else{
Inshow(root->lchild);
cout<<" "<data;
Inshow(root->rchild);
}
}
int main()
{
int n=10;
int a[10]={63,55,90,42,58,70,10,45,67,83};
int k=55;
//cout<<"Inpput the value you want to find:";
//cin>>k;
BiSortTree example(a,n);
example.Inshow();
cout<<"查找节点值为55的节点";
BiNode *p;
p=example.SearchBST(k);
if(p==NULL) cout<<"lll"<
//coutdata;
//example.DeleteBST(p->lchild,p);
example.Levershow();
cout<<"插入一个节点值为58的值:";
BiNode *s;
s->data=58;
example.InsertBST(s);
//example.Preshow();
return 0;
}
对于遍历算法可以不用考虑,只需看二叉排序树的建立上为什么建立不成功?