关于二叉树的问题
[bo]题目:[/bo]根据输入重构一个二叉树,输出按不同顺序遍历的节点序列数据输入:
第一行是一个整数N(1<=N<=20),表示有多少个测试例子,以下每行是一个测试例子。每个测试例子第一个是一个整数M,表示输出的遍历顺序,其中M=0,表示前序;M=1,表示中序;M=2,表示后序。然后是一个字符序列,字符序列由A-Z和#表示,A-Z表示节点,#表示空。如果字符所在字符串的位置为i(i为正整数,位置从1开始计数),则位置为i*2,i*2+1的节点为它的子节点。如果i*2,i*2+1超过字符串长度,表示子节点为空。
数据输出:
每行输出一个例子的结果。一个字符串,中间无空格。
示例:
输入文件名:input16.txt
2
0 AB#CD####EF
1 AB#CD####EF
输出:(标准输出)
ABCDEF
CBEDFA
[bo]我的程序:[/bo]
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define NULL 0
struct _bin_tree//二叉树结点
{
char data;
struct _bin_tree *lchild;
struct _bin_tree *rchild;
};
struct _bin_tree *T;
void Creat(struct _bin_tree *T,char s[],int num,int i)//由字符串构造二叉树
{
if(i>=num||s[i-1]=='#') T=NULL;
else
{
T= (struct _bin_tree *)malloc(sizeof(struct _bin_tree));
Creat(T->lchild,s,num,2*i);
Creat(T->rchild,s,num,2*i+1);
}
}
void Pre(struct _bin_tree *T)//先序遍历二叉树
{
if(T)
{
printf("%c",T->data);
Pre(T->lchild);
Pre(T->rchild);
}
}
void In(struct _bin_tree *T)//中序遍历二叉树
{
if(T)
{
In(T->lchild);
printf("%c",T->data);
In(T->rchild);
}
}
void Post(struct _bin_tree *T)//后序遍历二叉树
{
if(T)
{
Post(T->lchild);
Post(T->rchild);
printf("%c",T->data);
}
}
int main()
{
int M;
int N;
int i,lenth;
int j=1;
char s[100];
scanf("%d",&N);//输入测试例子个数N(1<=N<=20)
for(i=1;i<=N;i++)
{
scanf("%d%s",&M,s);//输入第i个测试例子
lenth=strlen(s);
Creat(T,s,lenth,j);
if(M==0) Pre(T);
else if(M==1) In(T);
else if(M==2) Post(T);
printf("\n");
}
return 0;
}
[bo]程序执行后没有输出二叉树的结点,我怀疑是构造二叉树时指针T就没有指向二叉树的根结点,但不知怎么改,放各位高手指教。[/bo]