遍历二叉树

/*

Description

根据输入重构一个二叉树，输出按不同顺序遍历的节点序列

数据输入：

第一行是一个整数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超过字符串长度，表示子节点为空。

数据输出：

每行输出一个例子的结果。一个字符串，中间无空格。

 

Sample Input

2

0 AB#CD####EF

1 AB#CD####EF

 

Sample Output

ABCDEF

CBEDFA

*/

#include<stdio.h>

void preorderTraverse(int count,int inCount,char* p,int i);
void inorderTraverse(int count,int inCount,char* p,int i);
void postorderTraverse(int count,char* p,int i);

int main(void)
{
    int cases,n,count,i;
    char c,temp;
    char p[10000];

    scanf("%d",&cases);

    while(cases--)
    {
        i = 1;
        p[0] = 'a';
        count = 0;
        scanf("%d",&n);
        temp = getchar();

//        p++;

        while((c = getchar()) != '\n')
        {
            p[i++] = c;
            count++;
        }

        if(0 == n)
        {
            preorderTraverse(count,count,p,1);
        }
        else if(1 == n)
        {
            inorderTraverse(count,count,p,1);
        }
        else if(2 == n)
        {
            postorderTraverse(count,p,1);
        }

        printf("\n");

    }
    return 0;
}


//编写先序遍历函数
void preorderTraverse(int count,int inCount,char* p,int i)
{
//    printf("%d",count);
    if(0 == inCount || 0 == count)
    {
        return;
    }

    inCount--;

    char temp = p[i];

    if(temp != '#')
    {
        printf("%c",temp);
    }
    if(2 * i <= count)
    {
        preorderTraverse(count,inCount,p,2*i);
    }

    if(2 * i + 1 <= count)
    {
        preorderTraverse(count,inCount,p,2*i+1);
    }
}


//编写中序遍历
void inorderTraverse(int count,int inCount,char*p,int i)
{
    if(0 == inCount || 0 == count)
    {
        return;
    }

    char temp = p[i];

    inCount--;

    if(2 * i <= count)
    {
        inorderTraverse(count,inCount,p,2*i);
    }

    if('#' != temp)
    {
        printf("%c",temp);
    }

    if(2 * i + 1 <= count)
    {
        inorderTraverse(count,inCount,p,2*i+1);
    }

}

//编写后续遍历  这里不要inCount这个变量
void postorderTraverse(int count,char*p,int i)
{
    if(0 == count)
    {
        return;
    }

    char temp = p[i];

    if(2 * i <= count)
    {
        postorderTraverse(count,p,2*i);
    }

    if(2 * i + 1 <= count)
    {
        postorderTraverse(count,p,2*i+1);
    }

    if('#' != temp)
    {
        printf("%c",temp);
    }
}