TZOJ 1222: 数据结构练习题――先序遍历二叉树 层次遍历

描述

给定一颗二叉树，要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

输入

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

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

输出

输出每棵二叉树的深度以及先序遍历二叉树得到的序列。

样例输入

2
1 -1
1 2 0 3 4 -1

样例输出

1 1
3 1 2 3 4

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct Bitnode {
 4     int val; //数据域 
 5     struct Bitnode *left,*right; //指针域，左子树和右子树 
 6 };
 7  
 8 struct Bitnode a[520]; //结构体数组存储 
 9 struct Bitnode* creat_level() //层次遍历 
10 {
11     int k=0,i,j,n;
12     while(scanf("%d",&n),n!=-1) //先按顺序从k=1存储每个结点的值，总共会有k个结点 
13         a[++k].val=n;
14     for(i=1,j=1;i<=k;i++,j++) //i第i个结点作为父节点的情况，j是代表父结点i在数组上和孩子距离j 
15     {//i+j就是i的左子树下标，i+j+1就是i的右子树下标 
16         if(i+j>k||a[i+j].val==0) a[i].left=NULL;//如果i的左子树下标越界或值为0，那么i的左子树为空 
17         else a[i].left=&a[i+j]; //否则让i的左子树指针指向i+j地址 
18         if(i+j+1>k||a[i+j+1].val==0) a[i].right=NULL; //如果i的右子树下标越界或值为0，那么i的右子树为空
19         else a[i].right=&a[i+j+1];//否则让i的右子树指针指向i+j+1地址 
20     }
21     return &a[1]; //下标1是根节点，返回根节点地址 
22 }
23 int maxdeep(Bitnode *root)
24 {
25     if(!root)return NULL; //
26     if(!root->left && !root->right)return 1; //如果根节点root的左右子树为空证明到底部了，深度返回1 
27     if(root->left)return maxdeep(root->left)+1; //根节点左子树不为空，那么递归左子树深度+1 
28     if(root->right)return maxdeep(root->right)+1;//根节点右子树不为空，那么递归右子树深度+1
29     return max(maxdeep(root->left),maxdeep(root->right))+1; //比较根节点左右子树的深度的较大值+1就是最大深度
30     //最小深度那就用min比较 
31 }
32 void xx(Bitnode *root) //先序根左右 
33 {
34     cout<<" "<<root->val; //根 
35     if(root->left)xx(root->left);//左 
36     if(root->right)xx(root->right);//右 
37 }
38 int main()
39 {    
40     int t;
41     cin>>t;
42     while(t--)
43     {
44         Bitnode *root = creat_level(); //层次构造二叉树并返回头结点root 
45         cout<<maxdeep(root);  
46         xx(root);
47         cout<<endl;
48     }
49      return 0;
50 }