题目描述
给定一颗二叉树，要求输出二叉树的前序遍历、后序遍历、中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。
输入要求
输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个……，如果某个结点不存在以0代替）
输出要求
输出每棵二叉树的前序遍历、后序遍历、中序遍历二叉树得到的序列。
假如输入
2 1 -1 1 2 0 3 4 -1
应当输出
1 1 1 1 2 3 4 3 4 2 1 3 2 4 1
Code:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84using namespace std;
typedef struct BTree
{
int data;
struct BTree *left;
struct BTree *right;
}BTree;
int arr[1010],n;
BTree* CreatBTree(int i)
{
if(i>=n||arr[i]==0)
return NULL;
BTree *temp=(BTree *)malloc(sizeof(BTree));
temp->data=arr[i];
temp->left=CreatBTree(2*i);
temp->right=CreatBTree(2*i+1);
return temp;
}
void preOrder(BTree *p)
{
if(p!=NULL)
{
cout<<p->data<<" ";
preOrder(p->left);
preOrder(p->right);
}
}
void inOrder(BTree *p)
{
if(p!=NULL)
{
inOrder(p->left);
cout<<p->data<<" ";
inOrder(p->right);
}
}
void postOrder(BTree *p)
{
if(p!=NULL)
{
postOrder(p->left);
postOrder(p->right);
cout<<p->data<<" ";
}
}
int getDeep(BTree *p)
{
int LD,RD;
if(p==NULL)
return 0;
LD=getDeep(p->left);
RD=getDeep(p->right);
return 1+max(LD,RD);
}
void delBTree(BTree *p)
{
if(p)
{
delBTree(p->left);
delBTree(p->right);
free(p);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
n=0;
while(cin>>arr[++n]&&arr[n]!=-1);
BTree *root=CreatBTree(1);
//cout<<getDeep(root);
//cout<<ceil(log(i-1.0)/log(2.0));//根据数组长度也可求得树的深度
preOrder(root);
cout<<endl;
postOrder(root);
cout<<endl;
inOrder(root);
cout<<endl;
delBTree(root);
}
return 0;
}
