Question

用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。

用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。

Answer 1

//上机题3，已在VC下调试成功。
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 30
typedef struct bnode{
char data;
struct bnode *lchild,*rchild;
}Bnode,*BTree;
typedef BTree DataType;
typedef struct{
DataType data[MAXSIZE];
int top;
}SeqStack,*PseqStack;//定义一个线性表栈
PseqStack Init_SeqStack(void)
{
PseqStack S;
S=(PseqStack)malloc(sizeof(SeqStack));
if(S)
S->top=-1;
return(S);
}//初始化栈。
int Empty_SeqStack(PseqStack S)
{
if(S->top==-1)
return(1);
else return (0);
}//判断是否栈空
int Push_SeqStack(PseqStack S,DataType x)
{
if(S->top==MAXSIZE-1)
return (0);
else
{
S->top++;
S->data[S->top]=x;
return (1);
}
}//入栈。
int Pop_SeqStack(PseqStack S,DataType *x)
{
if(Empty_SeqStack(S))
return (0);
else
{
*x=S->data[S->top];
S->top--;
return (1);
}
}//出栈。
BTree CreateBinTree(void)
{
BTree t;
char ch;
ch=getchar();
if(ch=='#') t=NULL;
else
{
t=(Bnode*)malloc(sizeof(Bnode));
t->data=ch;
t->lchild=CreateBinTree();
t->rchild=CreateBinTree();
}
return t;
}//创建一个二叉树。
void Visit(BTree t)
{
if(t!=NULL)
printf("%c ",t->data);
}//访问结点t。
void InOrder(BTree t)
{
if(t)
{
InOrder(t->lchild);
Visit(t);
InOrder(t->rchild);
}
}//二叉树的递归中序遍历。
int HighTree(BTree p)
{
int h1,h2;
if(p==NULL) return 0;
else
{
h1=HighTree(p->lchild);
h2=HighTree(p->rchild);
if(h1>h2) return (h1+1);
return (h2+1);
}
}//递归求二叉树的高度。
void PreOrder(BTree t)
{
PseqStack S;
BTree p=t;
S=Init_SeqStack();
while(p||!Empty_SeqStack(S))
{
if(p)
{
Visit(p);
Push_SeqStack(S,p);
p=p->lchild;
}
else
{
Pop_SeqStack(S,&p);
p=p->rchild;
}
}
}//二叉树的非递归先序遍历。

void main()
{
BTree T;
int a;
printf("输入二叉树的先序排列(空的地方输入#)：");
T=CreateBinTree();
printf("输出二叉树的先序遍历: ");
PreOrder(T);
printf("\n");
printf("输出二叉树的中序遍历: ");
InOrder(T);
printf("\n");
a=HighTree(T);
printf("二叉树的高度是： %d\n",a);
}
输入是输入12##346###5##