1407: 中序遍历二叉树

比眉伴天荒 2022-03-22 10:18 152阅读 0赞

### 题目描述 ###

给定一颗二叉树，要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。  
输入  
输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个…，如果某个结点不存在以0代替）  
输出  
输出每棵二叉树的深度以及中序遍历二叉树得到的序列。  
样例输入 Copy  
2  
1 -1  
1 2 0 3 4 -1  
样例输出 Copy  
1 1  
3 3 2 4 1  
题目链接：[http://120.78.162.102/problem.php?id=1407][http_120.78.162.102_problem.php_id_1407]

##### 分析: #####

本题，在我一开始的做的时候误将给出的序列看成了中序遍历的结果。  
在明确题意后，我们可以发现，因为是层序序列。所以我们应该用bfs的性质，从而依次赋值。在赋值过程中，需要不断地判断为0为-1的情况。  
然后，本题，在求深度的时候，我用到了完全二叉树的性质。但是，后来仔细思考过后，题目中给定的树，并不一定是完全二叉树，所以不可用。可以利用一个dfs来找到深度。  
代码如下：

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"stdlib.h"
    #define LEN sizeof(BiTree)
    typedef struct BiTree
    {
        int value;
        struct BiTree *LeftNode;
        struct BiTree *RightNode;
    }BiTree;
    //正式建树
    void CreateBiTree(BiTree **ROOT)
    {
        BiTree *Node[2000];
        BiTree *T;
        int value;
        int i,j;
        i=0;j=1;
        //这几条语句可以说是构建头结点的。
        scanf("%d",&value);
        *ROOT=(BiTree *)malloc(LEN);
        (*ROOT)->value=value;
        (*ROOT)->LeftNode=NULL;
        (*ROOT)->RightNode=NULL;
        Node[0]=*ROOT;
        //注意一次循环中需要把左右子树都考虑到。
        while(i<j)
        {
            scanf("%d",&value);
            if(value==-1)
                break;
            if(value!=0)
            {
                T=(BiTree *)malloc(LEN);
                T->value=value;
                T->LeftNode=NULL;
                T->RightNode=NULL;
                Node[j++]=T;
                Node[i]->LeftNode=T;
            }
            scanf("%d",&value);
            if(value==-1)
                break;
            if(value!=0)
            {
                T=(BiTree *)malloc(LEN);
                T->value=value;
                T->LeftNode=NULL;
                T->RightNode=NULL;
                Node[j++]=T;
                Node[i]->RightNode=T;
            }
         i++;
        }
    }
    //中序输出
    void InOrderTraverse(BiTree *T)
    {
        if(T==NULL)
            return ;
        InOrderTraverse(T->LeftNode);
        printf(" %d",T->value);
        InOrderTraverse(T->RightNode);
    
    }
    //求深度
    int dfs(BiTree *T)
    {
        int l,r;
        if(T==NULL)
            return 0;
        l=dfs(T->LeftNode)+1;
        r=dfs(T->RightNode)+1;
        return l>r?l:r;
    }
    int main()
    {
        int N,S;
        BiTree *ROOT;
        while(scanf("%d",&N)!=EOF)
        {
            while(N--)
            {
                ROOT=NULL;
                CreateBiTree(&ROOT);
                S=dfs(ROOT);
                printf("%d",S);
                InOrderTraverse(ROOT);
                printf("\n");
            }
        }
    }

[http_120.78.162.102_problem.php_id_1407]: http://120.78.162.102/problem.php?id=1407