回复 2# 的帖子
#include<iostream>
#include<queue>
using namespace std;
class bftree;
class bfnode
{
friend class bftree;
private:
int data;
bfnode *lchild,*rchild;
public:
bfnode(int x){data=x;lchild=rchild=0;}
};
///////////////////////////////////////////////
class bftree
{
private:
bfnode *root;
void print(bfnode *a);
public:
bftree(){root=0;}
bool IsEmpty();
bfnode* combine(bfnode *a,bfnode *b); //做二叉查找树的两个子树的合并
bool Insert(int x); //插入
bool Find(int x); //查找
void Delete(int x); //删除元素x
void ioPrint(){cout<<"中序："<<endl;print(root);cout<<endl;}//中序遍历驱动程序
void levelprint(); //层次遍历
};
//////////////////////
bool bftree::IsEmpty()
{
if(!root)
{
cout<<"empty"<<endl;
return true;
}
cout<<"not empty"<<endl;
return false;
}
/////////////////////////////
bool bftree::Insert(int x)
{
bfnode *y=new bfnode(x);
if(!root)
{
root=y;
return true;
}
bfnode *p,*q;
p=root;
q=0;
while(p)
{
q=p;
if(x<p->data)p=p->lchild;
else if(x>p->data)p=p->rchild;
else
{
//cout<<x<<"已经存在，不能插入"<<endl;
return false;
}
}
if(x<q->data)q->lchild=y;
else q->rchild=y;
return true;
}
////////////////////////////////
bool bftree::Find(int x)
{
bfnode *current=root;
while(current)
{
if(x<current->data)current=current->lchild;
else if(x>current->data)current=current->rchild;
else
{
return true;
}
}
return false;
}
/////////////////////////////
void bftree::Delete(int x)
{
bfnode *p=root,*q=0;
while(p)
{
if(x<p->data)
{
q=p;p=p->lchild;
}
else if(x>p->data)
{
q=p;p=p->rchild;
}
else break;
}
if(p)
{
cout<<x<<"在二叉查找树中，并将它删除"<<endl;
bfnode *pl,*pr,*a;//a作为新的根（子树）
pl=p->lchild;pr=p->rchild;
a=combine(pl,pr);
if(p==q->lchild)q->lchild=a;
else q->rchild=a;
}
else{cout<<x<<"不在二叉查找树中"<<endl;}
}
///////////////////////////////////////////
bfnode * bftree::combine(bfnode *a,bfnode *b)
{
if(!a)return b;
else if(!b)return a;
bfnode *p=a,*q=0;
while(p&&p->rchild)
{
q=p;
p=p->rchild;
}
q->rchild=p->lchild;
p->lchild=a;
p->rchild=b;
return p;
}
//////////////////////////////////////////////////////////
void bftree::print(bfnode *a)
{
if(a)
{
print(a->lchild);
cout<<a->data<<'\t';
print(a->rchild);
}
}
void bftree::levelprint()
{
cout<<"按层次："<<endl;
queue<bfnode *>myq;
bfnode *currentnode=root;
myq.push(currentnode);
while(!myq.empty())
{
currentnode=myq.front();
myq.pop();
cout<<currentnode->data<<'\t';
if(currentnode->lchild)myq.push(currentnode->lchild);
if(currentnode->rchild)myq.push(currentnode->rchild);
}
cout<<endl;
}
void main()
{
rand();
bftree bft;
bft.IsEmpty();
for(int i=0;i<20;i++)bft.Insert(rand());
bft.Insert(2222);
();
cout<<endl;
bft.levelprint();
int a=rand();
if(bft.Find(a))cout<<a<<"在二叉查找树中"<<endl;
else cout<<a<<"不在二叉查找树中"<<endl;
bft.Delete(2222);
();
cout<<endl;
bft.levelprint();
bft.Delete(1);
}
。。。你那边可以正常运行的吗？怎么我这里输入数后不能遍历输出来的？