树的遍历【PTA】

向右看齐 2023-10-03 17:42 14阅读 0赞

### 树的遍历 ###

树的遍历分为先序、中序、后序以及层序等等。  
以下题目来自PTA老师布置的题目。  
**题目**  
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

**输入格式：**  
输入第一行给出一个正整数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

**题目分析：**  
题目的思路大概分为两个方向：

1.  由后序和中序序列得到二叉树的模型
2.  求它的层序序列

**一： 由后序和中序序列得到二叉树的模型**  
由**后序序列最后一个元素为根** 和 \*\*中序根的左右部分就是它的子树 \*\*可推导

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16]  
则完整树为  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
可知其层序为 4 1 6 3 5 7 2

由以上推导过程可知，其就是一个递归不断找子树根的过程  
贴上代码

void dfs(int i, int j, int x, int y, int * a)
    //i,j是中序的起点和终点，x,y是后序的起点和终点
    {
        
    	if(i == j) {
        
    		* a = i;
    		return;
    	}
    	int t = i;
    	while(midOrder[t] != postOrder[y])t ++;
    	//postOrder[y]就是根，t就是根在中序序列中的位置
    	* a = t;         //将t赋值给a的指针域，第一次根结点
    	if(t == i)
    	{
        
            //此时无左子树，直接搜索右子树
    		dfs(i+1, j, x, y - 1, &r[t]); 
    	}
    	else if(t == j)
    	{
        
            //此时无右子树，直接搜索左子树
    		dfs(i, j-1, x, y - 1, &l[t]);
    	}
    	else {
        
            //左右子树依次往下搜索
    		dfs(i, t-1, x, x + t - i - 1, &l[t]);
    		dfs(t + 1, j, x + t - i, y -1, &r[t]);
    	}
    }

**二：求它的层序序列**  
层序：从上往下，从左往右一层一层的排序  
首先创造一个队列，传入根，将根的左右孩子入队，接着根弹出，依次将左右孩子的孩子入队，重复这个过程，模拟过程如下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
这样下来就相当于一层层的搜索了  
贴上代码

void rankOrder(int u)
    //层序遍历输出
    {
        
    	c.push(u);
    	while(!c.empty())
    	{
        
    		int h = c.front();  //从队首开始所有它的左右孩子
            //若左右孩子存在，则入队并输出
    		if(midOrder[l[h]]){
        
    			c.push(l[h]);
    			cout << ' ' << midOrder[l[h]];
    		}
    		if(midOrder[r[h]]){
        
    			c.push(r[h]);
    			cout << ' ' << midOrder[r[h]];
    		}
    		c.pop();        //队首弹出，新的队首就是他的兄弟或者他的孩子或者它的兄弟的孩子
    	}
    
    }

最后附上最终代码

#include<iostream>
    #include<algorithm> 
    #include<cstring>
    #include<queue>
    using namespace std;
    
    const int N = 31;
    int n;
    int postOrder[N],midOrder[N];//postOrder是后序，midOrder是中序序列
    int r[N],l[N];               //l,r数组分别模拟左右节点链表
    queue<int> c;                //队列,用于层序遍历输出
    
    void dfs(int i, int j, int x, int y, int * a)
    //i,j是中序的起点和终点，x,y是后序的起点和终点
    {
        
    	if(i == j) {
        
    		* a = i;
    		return;
    	}
    	int t = i;
    	while(midOrder[t] != postOrder[y])t ++;
    	//postOrder[y]就是根，t就是根在中序序列中的位置
    	* a = t;         //将t赋值给a的指针域，第一次根结点
    	if(t == i)
    	{
        
            //此时无左子树，直接搜索右子树
    		dfs(i+1, j, x, y - 1, &r[t]); 
    	}
    	else if(t == j)
    	{
        
            //此时无右子树，直接搜索左子树
    		dfs(i, j-1, x, y - 1, &l[t]);
    	}
    	else {
        
            //左右子树依次往下搜索
    		dfs(i, t-1, x, x + t - i - 1, &l[t]);
    		dfs(t + 1, j, x + t - i, y -1, &r[t]);
    	}
    }
    
    void rankOrder(int u)
    //层序遍历输出
    {
        
    	c.push(u);
    	while(!c.empty())
    	{
        
    		int h = c.front();  //从队首开始所有它的左右孩子
            //若左右孩子存在，则入队并输出
    		if(midOrder[l[h]]){
        
    			c.push(l[h]);
    			cout << ' ' << midOrder[l[h]];
    		}
    		if(midOrder[r[h]]){
        
    			c.push(r[h]);
    			cout << ' ' << midOrder[r[h]];
    		}
    		c.pop();        //队首弹出，新的队首就是他的兄弟或者他的孩子或者它的兄弟的孩子
    	}
    
    }
    int main(){
        
    	cin >> n;
    	int i;
    	for(i = 0; i < n; i++)cin >> postOrder[i];
    	for(i = 0; i < n; i++)cin >> midOrder[i];
    	
    	memset(r,-1,sizeof(r));
    	memset(l,-1,sizeof(l));
    	//初始化，-1表示空结点
    	int root;
    	dfs(0, n-1, 0, n-1, &root);
    	cout << midOrder[root] ;
    	rankOrder(root);
    	return 0;
    }

最后附上其先序输出的函数

void preOrderBiTree(int root)
    //先序输出
    {
        
    	if(l[root] != -1){
        
    		cout << ' ' << midOrder[l[root]] ;
    		preOrderBiTree(l[root]);
    	}
    	if(r[root] != -1){
        
    		cout << ' ' << midOrder[r[root]] ;
    		preOrderBiTree(r[root]);
    	}
    }

欢迎反馈。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dfe963cb3f0849e0a4dcd0c9b347a4bd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQUMgTWFrZXI=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/c45c13ae475b4b46bf43762084c3653c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQUMgTWFrZXI=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQUMgTWFrZXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/4a994e332b404af88fe38f74ff158ec1.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQUMgTWFrZXI=,size_20,color_FFFFFF,t_70,g_se,x_16