U5-10-二叉树3
原题链接：67324.4.0U5笔记合集
2025-10-18 16:46:01
发布于：江苏
4阅读
0回复
0点赞
一、上节课作业回顾
作业1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, l, r, g[N][3];
void pre_order(int x){
cout << x << ' ';
if (g[x][0]) pre_order(g[x][0]);
if (g[x][1]) pre_order(g[x][1]);
}
void in_order(int x){
if (g[x][0]) in_order(g[x][0]);
cout << x << ' ';
if (g[x][1]) in_order(g[x][1]);
}
void next_order(int x){
if (g[x][0]) next_order(g[x][0]);
if (g[x][1]) next_order(g[x][1]);
cout << x << ' ';
}
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> g[i][0] >> g[i][1];
}
pre_order(1);
cout<<endl;
in_order(1);
cout<<endl;
next_order(1);
return 0;
}
/*
输入：
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0
输出：
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1
7
1 2 7
2 4 0
3 0 0
4 0 3
5 0 0
6 0 5
7 6 0
*/
/*
[二叉树的遍历]
题目描述
有一个 n(n≤10^6) 个结点的二叉树。
给出每个结点的两个子结点编号（均不超过 n），
建立一棵二叉树（根节点的编号为 1），
如果是叶子结点，则输入 0 0。
建好树这棵二叉树之后，
依次求出它的前序、中序、后序列遍历。
输入格式
第一行一个整数 n，表示结点数。
之后 n 行，
第 i 行两个整数 l、r，
分别表示结点 i 的左右子结点编号。
若 l=0 则表示无左子结点，r=0 同理。
输出格式
输出三行，每行 n 个数字，用空格隔开。
第一行是这个二叉树的前序遍历。
第二行是这个二叉树的中序遍历。
第三行是这个二叉树的后序遍历。
*/
作业2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n;
char g[N][3];
void pre_order(char x){
cout << x;
if (g[x][0]) pre_order(g[x][0]);
if (g[x][1]) pre_order(g[x][1]);
}
int main(){
cin >> n;
char root;
for (int i=1; i<=n; i++){
string s;
cin >> s;
char a=s[0], b=s[1], c=s[2];
if (i == 1) root = a; //先找到根
if (b != '*') g[a][0] = b; //存左孩子
if (c != '*') g[a][1] = c; //存右孩子
}
pre_order(root);
return 0;
}
/*
题目描述
输入一串二叉树，输出其前序遍历。
输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。
特别地，数据保证第一行读入的节点必为根节点
空节点用 * 表示
输出格式
二叉树的前序遍历。
样例组
输入#1
6
abc
bdi
cj*
d**
i**
j**
输出#1
abdicj
*/
二、二叉树的构建
三、二叉树的构建（代码）
#include<bits/stdc++.h>
using namespace std;
//处理中序遍历为s，后序遍历为t的字串
void dfs(string s, string t)
{
if (s.size() == 0) return;
int id = s.find(t.back()); //找到后序遍历的最后一个字符(根节点)在中序遍历中的位置
cout << s[id]; //先输出，再递归左子树，再递归右子树
dfs(s.substr(0, id), t.substr(0, id));
//中序遍历的左子树是从下标0开始的id个字符，后序遍历的左子树是从下标0开始的id个字符
dfs(s.substr(id + 1, s.size() - id - 1), t.substr(id, s.size() - id - 1));
//中序遍历的右子树是从下标id+1开始的s.size() - id - 1个字符，后序遍历的右子树是从下标id开始的s.size() - id - 1个字符
}
int main()
{
string s, t;
cin >> s >> t;
dfs(s, t);
return 0;
}
这里空空如也
有帮助，赞一个