首页 > 其他分享 >TZOJ 4767: 二叉树遍历

TZOJ 4767: 二叉树遍历

时间:2023-03-01 21:11:24浏览次数:61  
标签:right TreeNode struct 二叉树 4767 TZOJ root left

描述

 

 

给定一颗二叉树,要求输出对二叉树进行先序和后序遍历所得到的序列。本题假设二叉树的结点数不超过1000。

 

 

输入

 

 

输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替),比如输入:

1 2 3 4 0 0 5 -1得到的二叉树如下:

 

 

 

输出

 

 

对应每组输入数据,输出有两行,第一行为二叉树的先序序列,第二行为二叉树的后序序列。

 

 

样例输入

 

2
1 -1
1 2 3 4 0 0 5 -1

样例输出

 

1
1
1 2 4 3 5
4 2 5 3 1

提示

 

输出的每个节点值后有一个空格。

#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left,*right;
};
 
struct TreeNode a[520];
int f; 
struct TreeNode* Creat(struct TreeNode* root)
{
    int k=0,i,j,n;
    while(scanf("%d",&n),n!=-1)
        a[k++].val=n;
    for(i=0,j=1;i<k;i++,j++)
    {
        if(i+j>=k||a[i+j].val==0) a[i].left=NULL;
        else a[i].left=&a[i+j];
        if(i+j+1>=k||a[i+j+1].val==0) a[i].right=NULL;
        else a[i].right=&a[i+j+1];
    }
    return &a[0];
}
void pretree(TreeNode *root)
{
    cout<<root->val<<" ";
    if(root->left)pretree(root->left);
    if(root->right)pretree(root->right);
}
void hx(TreeNode *root)
{
    if(root->left)hx(root->left);
    if(root->right)hx(root->right);
    cout<<root->val<<" ";
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        f = 1;
        struct TreeNode* root=NULL;
        root=Creat(root);
        pretree(root);
        cout<<endl; 
        f = 1;
        hx(root);
        cout<<endl;        
    }

    return 0;
}

 

标签:right,TreeNode,struct,二叉树,4767,TZOJ,root,left
From: https://www.cnblogs.com/jyssh/p/17169797.html

相关文章