数据结构练习题――中序遍历二叉树

逃离我推掉我的手 2023-07-13 11:00 87阅读 0赞

## 数据结构练习题――中序遍历二叉树 ##

**描述**  
给定一颗二叉树，要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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  
3 3 2 4 1

#include <iostream>
    #include<bits/stdc++.h>
    #include<algorithm>
    
    using namespace std;
    int node[1005],n;
    typedef struct tree{
        
        int data;
        struct tree *ltree,*rtree;
    }tree;
    void CreatTree(tree *&T,int x){
        
        if(node[x]==0)
        {
        
            T = NULL;
            return;
        }
        T = (tree *)malloc(sizeof(tree));
        T->data = node[x];
        CreatTree(T->ltree,2*x);
        CreatTree(T->rtree,2*x+1);
    }
    void InOrderTraverse(tree *T)
    {
        
        if(T)
        {
        
            InOrderTraverse(T->ltree);
            printf(" %d",T->data);
            InOrderTraverse(T->rtree);
        }
    }
    int Hight_Tree(tree *T){
        
        int l = 0,r = 0;
        if(T==NULL)
            return 0;
        l = Hight_Tree(T->ltree) + 1;
        r = Hight_Tree(T->rtree) + 1;
        return l>r?l:r;
    }
    int main(){
        
    int t;
    tree *T;
    T = NULL;
    scanf("%d",&t);
    while(t--)
    {
           int x;
        n=1;
        while(scanf("%d",&x)&&x!=-1)
        {
        
            node[n] = x;
            n++;
        }
        CreatTree(T,1);
        int len = Hight_Tree(T);
        printf("%d",len);
        InOrderTraverse(T);
        printf("\n");
    }
    return 0;
    }