当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > PAT L2-006. 树的遍历,patl2-006

PAT L2-006. 树的遍历,patl2-006

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

PAT L2-006. 树的遍历,patl2-006

L2-006. 树的遍历

时间限制 内存限制 代码长度限制 判题程序 作者
400 ms 65536 kB 8000 B Standard 陈越

  给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

新注册送38元体验金,输入格式:

输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

4 1 6 3 5 7 2

思路:

 根据二叉树的性质可以知道:

 可以根据这个规律,在中序遍历中找到根节点,再在后序遍历中利用根节点的位置得到左右子树各自的后序遍历以及长度。再根据他们各自的长度从中序遍历中分解得到左右子树各自的中序遍历。

比如样例中,中序遍历2 3 1 5 7 6 4的根节点就是4,然后在后序遍历1 2 3 4 5 6 7中根据根节点4的位置分得左子树的后序遍历1 2 3左子树长度为3,可在右子树的后序遍历5 6 7右子树长度为3。根据左右子树长度以及规律1可得到左右子树的中序遍历分别为2 3 15 7 6。以此类推就可将其全部分解。

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 struct tree//表示一棵树,记录他的中后序遍历数组和长路
 5 {
 6     int *h,*z,length;//h指向后序遍历的数组,z指向中序遍历的数组,length代表长度
 7     tree(int *h,int *z,int length)
 8     {
 9         this->h=h;
10         this->z=z;
11         this->length=length;
12     }
13     tree(){};
14 };
15 
16 queue<tree> Queue;//
17 int l;
18 int H[40];//储存后序遍历结果
19 int Z[40];//储存中序遍历结果
20 
21 void dis(tree T)
22 {
23     tree w;
24     int i;
25     int t;
26     Queue.push(T);
27     while(!Queue.empty())
28     {
29         w=Queue.front();
30         Queue.pop();
31         if(w.length>0)
32         {
33             t =w.h[w.length-1];//后序遍历的最后一个是根节点
34             cout << t;
35             int l = 0;
36             while(w.z[l]!=t)l  ;//得到左子树长度
37             if(l>0)//如果左子树存在就入队
38                             Queue.push(tree(w.h,w.z,l));
39             if(w.length-l-1)//如果右子树存在就入队,除了左子树和根节点剩下的就是右子树的长度
40                             Queue.push(tree(w.h l,w.z l 1,w.length-l-1));
41             if(!Queue.empty())cout << " ";//如果这时候队不为空说明后面还会输出节点,就要输出一个空格
42         }
43     }
44 }
45 
46 int main()
47 {
48     cin >> l;
49     int i;
50     i = 0;
51     while(i < l)
52     {
53         cin >> H[i];
54         i  ;
55     }
56     i = 0;
57     while(i < l)
58     {
59         cin >> Z[i];
60         i  ;
61     }
62     dis(tree(H,Z,l));
63     return 0;
64 }
65             

 

L2-006. 树的遍历,patl2-006 L2-006. 树的遍历 时间限制 内存限制 代码长度限制 判题程序 作者 400 ms 65536 kB 8000 B Standard 陈越 给定一棵二叉树...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:PAT L2-006. 树的遍历,patl2-006

关键词: