三种递归遍历二叉树

题目描述

给定一颗二叉树,要求输出二叉树的前序遍历、后序遍历、中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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
84
using 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;
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。