【数据结构习题】PTA 7-1 玩转二叉树 前序遍历+中序遍历_7-1 数据结构考题 二叉树的遍历-中序c语言编程题

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

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

输入样例：

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

输出样例：

4 6 1 7 5 3 2
1

和树的遍历那道题特别像

前序遍历+中序遍历思想：

知道这个思想之后，我们开始写前序遍历+中序遍历的代码：
也是递归思想

参考了树的遍历自己写的
递归里面的参数应该放什么每次都纠结死，说白了就是菜啦

Tree PreAndIn(int front1,int rear1,int front2,int rear2)
{
	Tree root=new struct TreeNode;
	root->data=Pre[front1];
	root->left=root->right=NULL;
	int p=front2;
	while(In[p]!=Pre[front1])
		p++;
	int num=p-front2;//左子树节点个数
	if(p!=front2) 
		root->left=PreAndIn(front1+1,front1+num,front2,p-1);
	if(p!=rear2)
		root->right=PreAndIn(front1+num+1,rear1,p+1,rear2);
	return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

镜面反转+层序遍历

其实这个就是将二叉树从上到下，从右到左（不是从左到右！！！） 输出，所以只需要将层序遍历函数里面，先往队列里面放右子树的值再放左子树的值：

void Change_Sequence(Tree root)
{
	queue<Tree> p;
	if(root)
		p.push(root);
	while(!p.empty())
	{
		root=p.front();
		p.pop();
		cout<<root->data;
		if(root->right)
			p.push(root->right);
		if(root->left)
			p.push(root->left);
		if(!p.empty())
		 	cout<<" ";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完整代码如下：

#include <bits/stdc++.h>
using namespace std;

int Pre[35],In[35];
typedef struct TreeNode
{
	int data;
	TreeNode *left;
	TreeNode *right;
}Node,*Tree ;

Tree PreAndIn(int front1,int rear1,int front2,int rear2)
{
	Tree root=new struct TreeNode;
	root->data=Pre[front1];
	root->left=root->right=NULL;
	int p=front2;
	while(In[p]!=Pre[front1])
		p++;
	int num=p-front2;//左子树节点个数
	if(p!=front2) 
		root->left=PreAndIn(front1+1,front1+num,front2,p-1);
	if(p!=rear2)
		root->right=PreAndIn(front1+num+1,rear1,p+1,rear2);
	return root;
}
void Change_Sequence(Tree root)
{
	queue<Tree> p;
	if(root)
		p.push(root);
	while(!p.empty())
	{
		root=p.front();
		p.pop();
		cout<<root->data;
		if(root->right)
			p.push(root->right);
		if(root->left)
			p.push(root->left);
		if(!p.empty())
		 	cout<<" ";
	}
}
int main()
{
	int n,i;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>In[i];
	}
	for(i=0;i<n;i++)
	{
		cin>>Pre[i];
	}
	Tree root=PreAndIn(0,n-1,0,n-1);
	Change_Sequence(root);
	return 0;
	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61