各位帮忙看看哪里出错了（有关二叉树的问题）
要求:1．创建以二叉链表作存储结构的二叉排序树；2．实现二叉排序树的查找、插入、删除和中序遍历操作。
程序：
//二叉树的主函数，文件名为bitreemain.cpp
#include<iostream>
#include<string>
#include"bisorttree.h"
using namespace std;
void main()
{
BiTree<string> bt; //创建一棵树
BiNode<string>* root = bt.Getroot( ); //获取指向根结点的指针
int s=-1;
while(s!=0)
{
cout<<"1.查找"<<endl;
cout<<"2.插入"<<endl;
cout<<"3.删除"<<endl;
cout<<"4.中序遍历"<<endl;
cout<<"0.退出"<<endl;
cin>>s;
switch(s)
{ case 1:
bt.SearchBST(root);
cout<<endl;
break;
case 2:
bt.InsertBstree(root);
cout<<endl;
break;
case 3:
bt.DeleteBST(root);
cout<<endl;
break;
case 4:
bt.InOrder(root);
cout<<endl;
break;
case 0:
exit(0);
}
}
}
//声明类BiTree及定义结构BiNode,文件名为bitree.h
#ifndef BITREE_H
#define BITREE_H
int num;
template <class T>
struct BiNode //二叉树的结点结构
{
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间
BiNode<T>* Getroot(); //获得指向根结点的指针
void InOrder(BiNode<T> *root); //中序遍历二叉树
BiNode* InsertBST(BiNode *root, BiNode *s); //在二叉排序树中插入一个结点s
void DeleteBST(BiNode *p, BiNode *f ); //删除结点f的左孩子结点p
BiNode* SearchBST(BiNode *root, int k, int count); //查找值为k的结点
void InsertBstree(BiNode *t,int x);
void empty( ); //判断二叉树是否为空
private:
BiNode<T> *root; //指向根结点的头指针
BiNode<T> *Creat( ); //有参构造函数调用
void Release(BiNode<T> *root); //析构函数调用
};
#endif
//定义类BiSortTree中的成员函数，文件名为bisorttree.cpp
#include<iostream>
#include<string>
#include"bisorttree.h"
using namespace std;
/*
*前置条件：二叉排序树不存在
*输 入：无
*功 能：构造一棵二叉树
*输 出：无
*后置条件：产生一棵二叉树
*/
bisorttree::bisorttree(int a[ ], int n)//构造函数
{
root = NULL;
for (int i = 0; i < n; i++)
{
BiNode* s = new BiNode;
s->data = a[i];
s->lchild = NULL;
s->rchild = NULL;
root = InsertBST(root, s);
}
}
/*
*前置条件：二叉排序树已经存在
*输 入：无
*功 能：释放二叉排序树中所有结点
*输 出：无
*后置条件：二叉排序树不存在
*/
bisorttree::~bisorttree(void)
{
Release(root);
}
/*
*前置条件：二叉排序树已经存在
*输 入：无
*功 能：获取指向根结点的指针
*输 出：指向根结点的指针
*后置条件：二叉排序树不变
*/
BiNode* bisorttree::Getroot( )
{
return root;
}
/*
*前置条件：空的二叉排序树
*输 入：指向根结点的指针和指向新建结点的指针
*功 能：将新建结点插入到二叉排序树中
*输 出：指向根结点的指针
*后置条件：产生一棵新的二叉排序树
*/
BiNode* bisorttree::InsertBST(BiNode *root, BiNode *s)
{
if(root==NULL) return s;
else{
if(s->data<root->data) root->lchild = InsertBST(root->lchild, s);//插入到左子树中
else root->rchild = InsertBST(root->rchild, s); //插入到右子树中
return root;
}
}
/*
*前置条件：二叉排序树已经存在
*输 入：指向结点f的指针和空指针p
*功 能：将结点f的左孩子结点p删除
*输 出：无
*后置条件：产生一棵新的二叉排序树
*/
void bisorttree::DeleteBST(BiNode *p, BiNode *f )
{
p = f->lchild;
BiNode *par;
BiNode *s;
if(!p->lchild && !p->rchild){ //p为叶子
f->lchild = NULL;
delete p;
}
else{
if (!p->rchild){ //p只有左子树
f->lchild = p->lchild;
delete p;
}
else{
if (!p->lchild){ //p只有右子树
f->lchild = p->rchild;
delete p;
}
else{ //左右子树均不空
par = p;
s = p->rchild;
while (s->lchild!=NULL) //查找最左下结点
{
par = s;
s = s->lchild;
}
p->data = s->data;
if (par==p) par->rchild = s->rchild; //处理特殊情况
else par->lchild = s->rchild; //一般情况
delete s;
} //左右子树均不空的情况处理完毕
}
}
}
/*
*前置条件：二叉排序树已经存在
*输 入：指向根结点的指针和查询的数据k
*功 能：查找数据值为k的结点
*输 出：指向数据值为k的结点
*后置条件：二叉排序树不变
*/
BiNode* bisorttree::SearchBST(BiNode *root, int k, int count)
{
if(root==NULL){
cout<<"此结点不存在!"<<endl;
cout<<"比较次数为"<<count<<endl;
return NULL;
}
else{
if (root->data==k){ //查找成功，返回
count++;
cout<<"查找"<<root->data<<"成功!"<<endl;
cout<<"比较次数为"<<count<<endl;
return root;
}
else{
if (k < root->data){
count++;
return SearchBST(root->lchild, k,count); //查找左子树
}
else{
count++;
return SearchBST(root->rchild, k,count); //查找右子树
}
}
}
}
/*
*前置条件：二叉排序树已经存在
*输 入：无
*功 能：释放二叉排序树的存储空间，析构函数调用
*输 出：无
*后置条件：二叉排序树不存在
*/
void bisorttree::Release(BiNode* root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
void InsertBstree(BiNode *t,int x)
{
BiNode f,p;
p=*t;
while (p) /*查找插入位置*/
{
if (x==p->key) return; /* 若二叉排序树t中已有key，则无需插入 */
f=p; /* f用于保存新结点的最终插入位置 */
p=(x<p->key)? p->lchild:p->rchild;
}
p=(BiNode) malloc(sizeof(bsnode)); /*生成待插入的新结点*/
p->key=x;
p->lchild=p->rchild=NULL;
if (*t==NULL) *t=p; /*原树为空*/
else
if (x<f->key)
f->lchild=p;
else f->rchild=p;
}
