打印二叉排序树

Question

题目如下：编写程序：建立一棵二叉排序树（要求以二叉链表方式存储），并要求输出排序结果。测试数据：H,A,X,F,T,B@（@结束标志）
希望输出形式为二叉排序树，即 A
B C
D E F G 这种分层的形式
C语言或者java都行 最好是c的 编译能通过的。非常感谢！

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NULL 0
#define MAXlevel 10
typedef struct BiTNode
{
char data[20];
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; /*用递归法建立二叉树*/
BiTree Create(BiTree T)
{
char ch[20];
scanf("%s",ch);
if(ch[0]==35)
T=NULL; /*用#表示某结点的左右子树是否为空，用于表示该结点是否为叶子或者可能存在左子树or右子树*/
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
strcpy(T->data,ch); /*输入T的data的值*/
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
} /*用先序的方法依次输入二叉树的结点的data值*/
return T;
}
void ShowTree(BiTree T,int deep) /*凹入表示法输出二叉树T，deep用于分层显示各节点的关系*/
{
deep++;
int i;
if(T==NULL)return ; /*递归结束*/
printf("\n%s ",T->data);
for(i=0;i<MAXlevel-deep;i++) printf("----"); /*输出各节点的线条*/
ShowTree(T->lchild,deep); /*打印左子树*/
ShowTree(T->rchild,deep); /*打印右子树*/
}
void Preorder(BiTree T)
{
if(T)
{
printf(" %s",T->data); /*输出根节点*/
Preorder(T->lchild);
Preorder(T->rchild);
} /*先序遍历*/
}
void zhongxu(BiTree T)
{
if(T){
zhongxu(T->lchild);
printf(" %s",T->data); /*递归左子树之后输出根节点*/
zhongxu(T->rchild);
}
} /*中序遍历*/
void houxu(BiTree T)
{
if(T)
{
houxu(T->lchild);
houxu(T->rchild);
printf(" %s",T->data); /*与先序遍历相反最后输出根节点*/
}
} /*后序遍历*/
void Levelorder(BiTree T) /*模拟队列先进先出的特点层次遍历二叉树*/
{
BiTNode *Queue[20],*b; /*定义结点的指针数组*/
int front,rear;
front=rear=0;
if (T)
{
Queue[rear++]=T; /*Queue[0]指向T，置rear=1*/
while (front!=rear)
{
b=Queue[front++]; /*b通过循环依次指向Queue[0],Queue[1],..*/
printf(" %s",b->data);
if(b->lchild!=NULL)
Queue[rear++]=b->lchild; /*通过循环将Queue[2*i+1](i=0,1,...),依次指向根结点的左子树、左子树的左子树...*/
if(b->rchild!=NULL)
Queue[rear++]=b->rchild; /*通过循环将Queue[2*i+1](i=0,1,...),依次指向根结点的左子树、左子树的左子树...*/
}
}
} /*层次遍历*/
void exchange(BiTree rt)/*交换二叉树的所有子树*/
{
BiTree temp = NULL;
if(rt->lchild == NULL && rt->rchild == NULL) return; /*若二叉树的左右子树均为空则返回*/

else
{
temp = rt->lchild;
rt->lchild = rt->rchild;
rt->rchild = temp;
} /*交换子树*/
if(rt->lchild)exchange(rt->lchild);
if(rt->rchild)exchange(rt->rchild); /*对二叉树的左右子树分别交换*/
} /*交换该二叉树所有子树*/
int DestroyBiTree(BiTree &T) /*删除二叉树T*/
{
if (T==NULL) return 1; /*当T为空的时候递归结束*/
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild); /*对左右子树进行操作*/
delete T;
T = NULL; /*删除并将T置为空*/
return 1;
} /*删除二叉树T*/
void findx(BiTree &T,char *ch)
{
if(strcmp(T->data,ch)==0)DestroyBiTree(T); /*判断树根的内容是否与字符串ch相同相同则删除整棵树*/
else if(T)
{
if(strcmp(T->lchild->data,ch)==0) /*判断其左孩子的内容是否与字符串ch相同*/
{
DestroyBiTree(T->lchild);
T->lchild =NULL;
return ; /*若相同则删去其左孩子及其子树然后将其双亲指向该结点的指针置空而后返回*/
}
if(strcmp(T->rchild->data,ch)==0)
{
DestroyBiTree(T->rchild);
T->rchild =NULL;
return ; /*判断其左孩子的内容是否与字符串ch相同，若相同则删去其左孩子及其子树然后将其双亲指向该结点的指针置空而后返回*/
}
}
else
{
findx(T->lchild,ch);
findx(T->rchild,ch); /*递归对其左右子树进行相同操作*/
}
} /*删除所输入结点及其子树*/
void main(){
char jiedian[20];
BiTree T;
int sum,dep;
T=Create(T);
printf("\n该树按照凹入表示法表示为：");
ShowTree(T,0); /*用凹入表示法打印该树*/
printf("\n\n该树的先序遍历序列为：\n");
Preorder(T); /*输出该树的先序遍历*/
printf("\n该树的中序遍历序列为：\n");
zhongxu(T); /*输出该树的中序遍历*/
printf("\n该树的后序遍历序列为：\n");
houxu(T); /*输出该树的后序遍历*/
printf("\n该树的层次遍历序列为\n");
Levelorder(T);
printf("\n\n交换左右子树后的树按照凹入表示法表示为：");
exchange(T);
ShowTree(T,0); /*用凹入表示法打印交换所有子树后的得到树*/
printf("\n请输入待删除结点内容：\n");
scanf("%s",jiedian);
findx(T,jiedian); /*删除所输入结点及其子树*/
printf("删除所输入结点及其子树后的二叉树用凹入法表示为：");
ShowTree(T,0); /*用凹入法表示法输出删除所要求结点及其子树之后的二叉树*/
printf("\n");
}

参考使用，请勿照抄！

参考资料：翻版盗用，违者不究！

本回答被提问者采纳