特殊二叉树
原题链接：67324.4.0U5笔记合集
2025-10-25 16:33:36
发布于：江苏
16阅读
0回复
0点赞
一. 上节课作业
T2.
#include<bits/stdc++.h>
using namespace std;
//处理前序遍历为s，中序遍历为t的字串
void dfs1(string s, string t) {
if (s.size() == 0) return;
int id = t.find(s[0]);//找到前序遍历的第一个字符(根节点)在中序遍历中的位置
dfs1(s.substr(1, id), t.substr(0, id));//前序遍历的左子树是从下标1开始的id个字符，中序遍历的左子树是从下标0开始的id个字符
dfs1(s.substr(id + 1, s.size() - id - 1), t.substr(id + 1, s.size() - id - 1));//前序遍历的右子树是从下标id+1开始的s.size() - id - 1个字符，中序遍历的右子树是从下标id+1开始的s.size() - id - 1个字符
cout << s[0];
}
//处理中序遍历为s，后序遍历为t的字串
void dfs2(string s, string t) {
if (s.size() == 0) return;
int id = s.find(t.back());//找到后序遍历的最后一个字符(根节点)在中序遍历中的位置
cout << s[id];//先输出，再递归左子树，再递归右子树
dfs2(s.substr(0, id), t.substr(0, id));//中序遍历的左子树是从下标0开始的id个字符，后序遍历的左子树是从下标0开始的id个字符
dfs2(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() {
int _;
cin >> _;
while (_--) {
int opt;
string s, t;
cin >> opt >> s >> t;
if (opt == 1) {
dfs1(s, t);
}
else {
dfs2(s, t);
}
cout << '\n';
}
return 0;
}
二. 完全二叉树的叶子节点
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct node{
int v, l, r;
void in(){
cin>>v>>l>>r;
}
}a[N];
int n;
void preOrder(int rt){
if (a[rt].l==0 && a[rt].r==0){
cout << a[rt].v << ' '; //输出根结点的value
}else{
if (a[rt].l) preOrder(a[rt].l);
if (a[rt].r) preOrder(a[rt].r);
}
}
int main(){
cin >> n;
for (int i=1; i<=n; i++) a[i].in(); //成员方法,成员函数
preOrder(1);
// gameOverFirst //小驼峰命名法
// GameOverFirst //大驼峰命名法
// game_over_first //蛇形命名法
return 0;
}
三. BST
四. 哈夫曼树
这里空空如也
有帮助，赞一个