|
|
二叉树有四种遍历方法：先序遍历，中序遍历，后序遍历，层次遍历
先序遍历是指以访问根节点，先序遍历左子树，先序遍历右子树为顺序的遍历方法
中序遍历是指以中序遍历左子树，访问根节点，中序遍历右子树为顺序的遍历方法，知道他与其他任意一种遍历方法就能求得除了他们以外的其他任意一种遍历方法
后序遍历是指以后序遍历左子树，后序遍历右子树，访问根节点为顺序的遍历方法
层次遍历，顾名思义就是按层去遍历，很像搜索里的广度优先搜索
看一道例题：1367https://oj.singera.cn/dist/quesInfo?solution_id=70988&problem_id=1367
这道题已知中序遍历，先序遍历，刚才讲过只要有中序遍历且大于等于两个遍历方法，就可以用一个函数来求
void aaa(int xian_head,int xian_end,int zhong_head,int zhong_end){
int gen=0;
return;
}
参数里设定先序的head和end，中序的head和end
变量根不是整个而叉树的根，而是剩下没有遍历到的子树的根
参考不完全代码（希望查错）：
void aaa(int xian_head,int xian_end,int zhong_head,int zhong_end){
int gen=0;
for(int i=zhong_head;i<=zhong_end;++i)
if(xian[xian_head]==zhong){
gen=i;
break;
}
if(gen>zhong_head) aaa(xian_head+1,xian_head+gen-zhong_head,zhong_head,gen-1);
if(gen<zhong_end) aaa(xian_head+gen-zhong_head+1,xian_end,gen+1,zhong_end);
cout<<zhong[gen];
return;
}
1370https://oj.singera.cn/dist/quesInfo?problem_id=1370
也是同理
|
|
发表于 2023-3-21 19:44:34
置顶卡
楼主
发表于 2023-3-22 00:38:20