U5-8-9-二叉树2

原题链接：67324.4.0U5笔记合集

1943

2025-10-08 15:57:34

发布于：江苏

6阅读

0回复

0点赞

一、二叉树的三种遍历方式

先序遍历：【根】左右
中序遍历：左【根】右
后序遍历：左右【根】

二、二叉树的后续遍历代码实现

递归实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5; 
int a[N], n;

void dfs(int root){
	//先序遍历: 根左右 先输出根 
	cout << a[root] << ' ';
	//递归左孩子 2*root
	if (2*root <= n) dfs(2*root);
	//递归右孩子 2*root+1 
	if (2*root+1<=n) dfs(2*root+1);
} 

int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin>>a[i];
	
	dfs(1); 

	return 0;
}

/*
[【二叉树】前序遍历]
题目描述
给出一个数组，
将这个数组构造成一个二叉树，即根节点为数组下标为 1 的位置，
数组下标为 x 结点的左儿子结点是 2*x，右儿子是 2*x+1。

输出二叉树前序遍历结果。

输入格式
第一行一个 n(1≤n≤1e5)，表示数组的长度
第二行 n 个数 ai (1≤ai ≤1e9)。

输出格式
输出二叉树前序遍历结果。

样例组
输入#1
3
1 2 3

输出#1
1 2 3

*/