自己写的二叉排序树，实现结点插入，查找，删除功能；但是始终有问题，就大神们帮帮忙，帮我调试成功！
RT，
只能插入2个结点，插入第3个就把第2个覆盖了，不知道是什么情况。
代码如下：
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
using namespace std;
typedef struct BiTNode
{
int data;
struct BiTNode* lChild;
struct BiTNode* rChild;
} BSTree,BTNode;
//查找key值
bool Search(BSTree*& Btree,int key ,BSTree*& father ,BSTree*& p)
{
if(!Btree)
{
p=father;
return false;
}
else if(Btree->data==key)
{
p=Btree;
return true;
}
else if(Btree->data<key)
{
return Search(Btree->lChild,key,Btree,p);
}
else
{
return Search(Btree->rChild,key,Btree,p);
}
}
//插入结点
bool InsertBST(BSTree*& Btree,BSTree*& p,int& key)
{
BSTree* s=NULL;
if(!Search(Btree,key,Btree,p))
{
s=(BTNode*)malloc(sizeof(BTNode));
s->data=key;
s->lChild=NULL;
s->rChild=NULL;
if(!p) Btree=s;
else if(p->data > key)
{
p->lChild=s;
}
else
{
p->rChild=s;
}
return true;
}
else
return false;
}
//删除结点
bool deleteBST(BSTree*& Btree,int& key)
{
BSTree* p=NULL;
BSTree* f=Btree;
if(Search(Btree,key,f,p))
{
if(p->lChild==NULL &&p->rChild==NULL ) //叶结点
{
if(f->data>p->data) f->lChild=NULL;
else f->rChild=NULL;
free(p);
}
else if(p->rChild==NULL) //有左孩子
{
if(f->data > p->data) f->lChild=p->lChild;
else f->rChild=p->lChild;;
free(p);
}
else if(p->lChild==NULL) //有右孩子
{
if(f->data > p->data) f->lChild=p->rChild;
else f->rChild=p->rChild;;
free(p);
}
else //左右孩子都不为空
{
//找到p结点左子树中最右边的结点
BSTree* n=p->lChild;
while(n->rChild!=NULL)
{
if(n->rChild==NULL)
{
break;
}
n=n->rChild;
}
n->rChild=p->rChild;//将P结点右孩子设为p结点左子树中最右边的结点的右孩子
//指定左孩子为p结点父结点f的孩子结点
if(f->data > p->data) f->lChild=p->lChild;
else f->rChild=p->lChild;;
free(p);
}
return true;
}
return false;
}
//中序线索化,找到某个结点的前驱节点
//中序线索化,找到某个结点的houji节点
//中序遍历二叉树
void InOrder(BSTree* Btree)
{
//printf("Print1");
if(Btree)
{
//printf("Print2");
InOrder(Btree->lChild);
printf("%d\t",Btree->data);
InOrder(Btree->rChild);
}
}
int main()
{
BSTree* BTree=NULL;
while(1)
{
int mode =0;
printf("Input your mode(1:插入,2:删除,3:查找,4:中序打印):\n");
scanf("%d",&mode);
if(mode>4 || mode<1 )
{
printf("Wrong Mode! Must between 1 and 4\n");
continue;
}
switch(mode)
{
case 1:
{
int key=0;
BTNode* p=NULL;
printf("Input a number to insert into BST:");
scanf("%d",&key);
bool bflag=InsertBST(BTree,p,key);
if(bflag)
{
printf("插入元素成功!");
}
else
{
printf("插入元素失败!");
}
if(!BTree) printf("BTree empty!\n");
printf("\n");
}
break;
case 2:
{
int key=0;
printf("Input a number to delete from BST:");
scanf("%d",&key);
if(deleteBST(BTree,key))
{
printf("删除元素成功!");
}
else
{
printf("删除元素失败!");
}
printf("\n");
}
break;
case 3:
{
int key=0;
printf("Input a number to search from BST:");
scanf("%d",&key);
BSTree* p=NULL;
if(Search(BTree,key,BTree,p))
{
printf("查找元素成功,%d",p->data);
}
else
{
printf("查找元素失败!");
}
printf("\n");
}
break;
case 4:
{
//printf("Print BST\n");
//if(BTree) printf("Can print\n");
InOrder(BTree);
printf("\n");
}
break;
default:
break;
}
}//end while
return 0;
}
else if(Btree->data<key)
{
return Search(Btree->rChild,key,Btree,p);
}
else
{
return Search(Btree->lChild,key,Btree,p);
}
