树的遍历（概念与习题）

亦凉 2023-07-24 08:55 8阅读 0赞

树的遍历概念  
首先我们观察三种遍历方式对根、左、右结点的遍历顺序  
先序的遍历顺序：根 – 左 – 右  
中序的遍历顺序：左 – 根 – 右  
后序的遍历顺序：左 – 右 – 根

遍历顺序可以理解为 **优先级**  
先序遍历举例：  
若一个节点有左子树和右子树，那它下一步将会先走向左子树，等到左子树的全部节点遍历完了，它才会遍历右子树。

现在我们来判断下面这棵树的先序遍历  
![树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
树的先序遍历顺序：GDAFEMHZ  
当然，树的中序遍历与先序遍历相似：有左子树就先遍历，若没有左子树则遍历节点的根，再遍历右子树。  
树的中序遍历顺序：ADEFGHMZ  
树的后序遍历顺序：AEFDHZMG

习题练习

#### ①求先序排列 ####

题目描述  
已知树的中序和后序，求先序。  
输入  
BADC  
BDCA  
输出  
ABCD

--------------------

**解题思路**  
①、先序遍历是从根开始的，我们可以通过后序找到树的根，再通过中序得到左子树、右子树。  
②、先遍历左子树、再遍历右子树的方式不断找子树的根结点并输出，最终得到先序遍历。

**样例分析**  
题目提供：中序ACGDBHZKX，后序CDGAHXKZB。  
①、找到主根B；  
②、由于中序遍历的性质，我们可以得到左子树 ACGD和右子树 HZKX。  
③、对应可找到后序遍历CDGA和HXKZ（从头找即可）  
从而问题就变成求左子树再求右子树：  
左子树中序遍历ACGD，后序遍历CDGA。  
右子树中序遍历HZKX， 后序遍历HXKZ。  
接着递归，按照①~③步骤。  
找到左子树的根A，再分为两棵子树。右子树的根Z，再分为两棵子树。  
就按这样一直做下去（先输出根，再递归）。

模板:  
step1:找到根并输出  
step2:将中序，后序各分为左右两棵子树；  
step3:递归，重复step1,2；

//不断找根结点 
    #include<bits/stdc++.h>
    using namespace std;
    
    void dfs(string s1, string s2)
    { 
    	char gen = s2[s2.length()-1];	//根结点 
    	int k = s1.find(gen);	//在中序字符串中查找字符gen并得到下标
    	if(k==s1.npos) return;	//查找不到
    	cout<<gen;
    	
    	string s3, s4, s5, s6;
    	//左子树
    	s3 = s1.substr(0, k);	//1子树的中序
    	s4 = s2.substr(0, k);	//1子树的后序 
    	dfs(s3, s4);
    	//右子树
    	s5 = s1.substr(k+1);	//2子树的中序 
    	s6 = s2.substr(k, s1.length()-1-k);	//2子树的后序 
    	dfs(s5, s6);
    }
    
    int main()
    { 
    	string s1, s2;
    	cin>>s1>>s2;	//中序、后序 
    	dfs(s1, s2);
    	
    	return 0;
    }

#### ②求后序排列 ####

已知树的先序和树的中序，求后序。  
输入  
ABEDFCHG  
CBADEFGH  
输出  
AEFDBHGC

--------------------

#include<bits/stdc++.h>
    using namespace std;
    
    //主要是确定输出的时机 
    void dfs(string prior, string mid){ 
    	if(prior.length()==0){ 
    		return;
    	}
    	int p = mid.find(prior[0]);
    	dfs(prior.substr(1, p), mid.substr(0, p));	//找左子树 
    	dfs(prior.substr(p+1), mid.substr(p+1));	//找右子树 
    	cout<<prior[0];		//找不到左子树与右子树或已找完
    }
    
    int main(){ 
    	string mid, prior;
    	cin>>mid>>prior;
    	dfs(prior, mid);
    	
    	return 0;
    }

--------------------

**解题思路**  
[洛谷题解][Link 1]  
举例：  
中序遍历为：ABEDFCHG，前序遍历为：CBADEFGH。  
那么根节点就是C。  
于是找到了中序遍历的左子树：ABEDF 和右子树：HG。  
紧接着，前序遍历找到了左子树：BADEF 和右子树：GH。  
于是，我们可以继续递归下去，直至字符串为空。

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230528/c3964d0ddd134d0a98588a75ffa42175.png
[Link 1]: https://www.luogu.com.cn/problem/solution/P1827