|
建立二叉排序树后,选择先序遍历,无输出。。。
我对指针方便不太熟悉,感觉应该是那方面出错。。。
请高人解救
#include<stdio.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef int KeyType;
typedef struct BiTNode
{ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree p)
/*查找二叉排序树T中关键字等于key的数据元素,若查找成功,p指向该数据元素结点,
并返回TRUE,否则p指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲,
其初始调用值为NULL*/
{if(!T) {p=f;return FALSE;} /*查找不成功*/
else if EQ(key,T->data) {p=T;return TRUE;} /*查找成功 */
else if LT(key,T->data)
return SearchBST(T->lchild,key,T,p); /*在左子树中继续查找 */
else return SearchBST(T->rchild,key,T,p); /*在右子树中继续查找*/
}
Status InserBST(BiTree T, ElemType e)
/*当二叉排序树T中不存在关键字等于e的数据元素时,插入e并返回TRUE,否则返回FALSE */
{BiTree p; BiTree s ;
if(!SearchBST(T,e,NULL,p))
{
s=(BiTNode*)malloc(sizeof(BiTNode));
s->data=e; s->lchild=s->rchild=NULL;
if(!p)T=s; /*若p为空,则*S为新的根节点*/
else if LT(e,p->data)p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}
Status CreateBST(BiTree T) /*建立一棵二叉排序树,T指向根结点*/
{KeyType key;
T=NULL;
printf("Please input your data:\n");
scanf("%d",&key);
while(key) /*当key=0时结束 */
{InserBST(T,key);
scanf("%d",&key);
}
return T;
}
void DestroyDSTable(BiTree DT) /*销毁动态查找表DT*/
{if(DT=NULL)return OK;
if(DT->lchild) /*存在左孩子*/
DestroyDSTable(DT->lchild); /*销毁左孩子子树*/
if(DT->rchild)
DestroyDSTable(DT->rchild); /*销毁右孩子子树*/
free(DT); /*释放根节点*/
DT=NULL;
}
Status DeleteBST(BiTree T,KeyType key)
/*若二叉排序树Tzong存在关键字等于key的数据元素时,则删除该元素结点,并返回TRUE;否则返回FALSE*/
{if(!T) return FALSE;
else{
if (EQ(key,T->data)) return Delete(T);
else if (LT(key,T->data)) return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
}
}
Status Delete(BiTree p) /*从二叉排序树中删除结点p,并重接它的左或右子树*/
{BiTree q,s;
if(!p->rchild)
{q=p;p=p->lchild;free(q);} /*右子树空*/
else if (!p->lchild)
{q=p;p=p->rchild;free(q);} /*左子树空*/
else /*左右子树均不空*/
{q=p;s=p->lchild;
while(s->rchild){q=s;s=s->rchild;} /*向右到尽头*/
p->data=s->data;
if(q!=p)q->rchild=s->lchild; /*重接*q的右子树*/
else q->lchild=s->lchild; /*重接*q的左子树*/
}
return TRUE;
}
Status PrintElement(ElemType e) /*输出元素e*/
{printf(" %d ",e);return OK;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType d))
/*先序遍历二叉树,对每个数据元素调用函数Visit*/
{ if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
} else return OK;
}
Status InOrderTraverse(BiTree T,Status (*Visit)(ElemType d))
/*中序遍历二叉树,对每个数据元素调用函数Visit*/
{
if(T){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}else return OK;
}
main()
{BiTree bt;int a,e,k;
printf("1.Creat a BSTree\n");
printf("2.Insert a data\n");
printf("3.Destroy the tree\n");
printf("4.PreOrderTraverse\n");
printf("5.InOrderTraverse\n");
printf("6.DeleteBST\n");
m:scanf("%d",&a);
switch(a)
{ case 1:bt=CreateBST(bt);break;
case 2:printf("input data:/n");
scanf("d",&e);
InserBST(bt,e);break;
case 3:DestroyDSTable(bt);break;
case 4:PreOrderTraverse(bt,PrintElement);break;
case 5:InOrderTraverse(bt,PrintElement);break;
case 6:printf("input delete data:");scanf("%d",&k);
DeleteBST(bt,k);
}
goto m;
getch();
} |
|