DFS在二叉树上的表现
  YYlZHciH2BRm 2024年03月02日 36 0
C++

原题跳转:洛谷B3642 二叉树的遍历
题目内容:

二叉树的遍历

题目描述

有一个 \(n(n \le 10^6)\) 个结点的二叉树。给出每个结点的两个子结点编号(均不超过 \(n\)),建立一棵二叉树(根节点的编号为 \(1\)),如果是叶子结点,则输入 0 0

建好树这棵二叉树之后,依次求出它的前序、中序、后序列遍历。

输入格式

第一行一个整数 \(n\),表示结点数。

之后 \(n\) 行,第 \(i\) 行两个整数 \(l\)\(r\),分别表示结点 \(i\) 的左右子结点编号。若 \(l=0\) 则表示无左子结点,\(r=0\) 同理。

输出格式

输出三行,每行 \(n\) 个数字,用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。

样例 #1

样例输入 #1

7
2 7
4 0
0 0
0 3
0 0
0 5
6 0

样例输出 #1

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

\(\huge\color{red}\text{题解}\)

#include <cstdio>
#include <iostream>
using namespace std;
const int R=1e6+1;//数据范围
int n;
struct tree//定义一棵树
{
	int l,r;//左子节点,右子节点
}arr[R];
void Fdfs(int x)//前序遍历
{
	if (x==0)	return ;
	cout<<x<<' ';
	Fdfs(arr[x].l);
	Fdfs(arr[x].r);
	return ;
}
void Mdfs(int x)//中序遍历
{
	if (x==0)	return ;
	Mdfs(arr[x].l);
	cout<<x<<' ';
	Mdfs(arr[x].r);
	return ;
}
void Ddfs(int x)//后序遍历
{
	if (x==0)	return ;
	Ddfs(arr[x].l);
	Ddfs(arr[x].r);
	cout<<x<<' ';
	return ;
}
int main()
{	
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		cin>>arr[i].l>>arr[i].r;
	Fdfs(1);printf("\n"); 
	Mdfs(1);printf("\n"); 
	Ddfs(1);
	return 0;
}

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: pair 下一篇: 网狐核心源码阅读分析
  1. 分享:
最后一次编辑于 2024年03月02日 0

暂无评论

推荐阅读
  8ZfKOql7qM9w   15天前   9   0   0 C++
  mCuLBwVLn3Lu   13天前   16   0   0 C++
YYlZHciH2BRm
作者其他文章 更多