首页 > 其他分享 >DFS在二叉树上的表现

DFS在二叉树上的表现

时间:2024-03-02 17:55:05浏览次数:29  
标签:结点 遍历 int 表现 arr DFS 二叉树 前序

原题跳转:洛谷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;
}

标签:结点,遍历,int,表现,arr,DFS,二叉树,前序
From: https://www.cnblogs.com/Hzj1007/p/18048989

相关文章

  • 不同序构造二叉树
    一、根据前序与中序构造二叉树前序遍历:确定根节点root,最左端的节点即为根节点中序遍历:确定根节点左右两边的节点,通过计算左右两边节点集合的大小对root左节点集合与右节点集合执行重复操作,不断确定小集合的根节点,最终可构造出一整棵二叉树树的存储可以采用定义类或结构体,这......
  • 94. 二叉树的中序遍历c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*//***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/voidinorder(structTre......
  • 145. 二叉树的后序遍历c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*//***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/voidpostorder(structT......
  • 144. 二叉树的前序遍历c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*//***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/voidpreorder(structTr......
  • leedcode 二叉树的前序遍历
    递归法:classSolution:def__init__(self):#初始化一个实例变量res用于存储前序遍历结果self.res=[]defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:#如果根节点存在ifroot:#检查根......
  • hdfs文件传输到ods层的脚本
     #!/usr/bin/python3#coding=utf-8importsysfrombaseimportget_yesterday,APPimportsubprocessdate=get_yesterday()tables=['ods_log_inc','ods_activity_info_full','ods_activity_rule_full','ods_base_categ......
  • CentOS7 安装FastDFS配置详解
    一、介绍FastDFS是一个开源的高性能分布式文件系统。它的主要功能包括:文件存储,文件同步和文件访问(文件上传和文件下载),它可以解决高容量和负载平衡问题。FastDFS应该满足基于照片共享站点和视频共享站点等文件的网站的要求。FastDFS具有两个角色:tracker和storage。tracker负责调......
  • 关于dfs序求lca的一点思考
    最近学了一点黑科技,这就是一个。有一个结论比如这就是一个dfn序。在代码中,常常对beg和ed都开一个数组。如果一个点是x,y的lca记为g,那么有以下结论\(beg[g]<min(beg[x],beg[y]),ed[g]>max(ed[x],ed[y])\)感性理解即可。所以我们就可以在符合的点找深度最大的。这是一种思路,常常......
  • hdfs基本命令
    创建目录hadoopfs–mkdir[-p]<path>查看目录下的内容hadoopfs–ls[-h][-R][<path>]-h人性化显示文件大小-R递归查看指定目录及子目录上传文件hadoopfs–put[-f][-p]<localsrc><dst>-f覆盖目标文件(若文件已存在)-p保留访问和修改时间、......
  • 平衡二叉树
    平衡二叉树特点:任意节点左右子树的高度不超过1反例:10节点的左子树高度为0,右子树高度为3这是平衡二叉树这也是平衡二叉树如何保持平衡添加一个节点后,该树不再是平衡二叉树-》旋转左旋,多余左节点做右节点复杂的左旋10的多余左节点9。给予前父节点7作为右节......