二叉树
一些定义
-
先序，中序，后序遍历中的序是遍历根的顺序
-
层序遍历就是这个数的bfs序列
树的存储
有很多种存储方式，一般用结构体数组。
数组下标对应这个数的结点，既可以存左儿子右兄弟又可以存左儿子右儿子。
下面来看一些题真切的感受一下代码
例题1 遍历完全二叉树
http://oj.daimayuan.top/course/7/problem/430
题目
给你一棵 n 个节点的完全二叉树，节点的编号为 1 到 n，二叉树的根为 1 号节点。编号为 i (1≤i≤n) 的节点的左儿子如果存在的话，编号为 i+i；编号为 i (1≤i≤n) 的节点的右儿子如果存在的话，编号为 i+i+1。
现在请你求出这棵完全二叉树的先序、中序和后序遍历的结果。
输入格式
一行一个整数 n。输出格式
输出三行，每行 n 个数代表一种遍历的结果。第一行为先序遍历的结果，第二行为中序遍历的结果，第三行为后序遍历的结果。
样例输入
7
样例输出
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
数据规模
对于所有数据，保证 1≤n≤1024。
代码
#include<bits/stdc++.h>
using namespace std;
int a[2000];
int n;
void preorder(int x) //先序
{
if(x>n) return;
cout<<x<<" ";
preorder(2*x);
preorder(2*x+1);
}
void inorder(int x) //中序
{
if(x>n) return;
inorder(2*x);
cout<<x<<" ";
inorder(2*x+1);
}
void postorder(int x) //后序
{
if(x>n) return;
postorder(2*x);
postorder(2*x+1);
cout<<x<<" ";
}
int main()
{
cin>>n;
preorder(1);
cout<<endl;
inorder(1);
cout<<endl;
postorder(1);
return 0;
}
例题2遍历一般二叉树
http://oj.daimayuan.top/course/7/problem/431
题目
给你一棵 n 个节点的二叉树，节点的编号为 1 到 n，二叉树的根为 1 号节点。请你求出这棵二叉树的先序、中序和后序遍历的结果。
输入格式
第一行一个整数 n 表示节点数。接下来 n 行，每行两个整数，第一个整数表示 i 号节点的左儿子的编号，第二个整数表示 i 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。
输入保证是一棵二叉树。
输出格式
输出三行，每行 n 个数代表一种遍历的结果。第一行为先序遍历的结果，第二行为中序遍历的结果，第三行为后序遍历的结果。
样例输入
4
2 3
0 0
4 0
0 0
样例输出
1 2 3 4
2 1 4 3
2 4 3 1
数据规模
对于所有数据，保证 1≤n≤1024。
代码
# include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1200;
pii a[N];
int n;
void preorder(int x)
{
if(x>n || x == 0) return ;
cout<<x<<" ";
preorder(a[x].first);
preorder(a[x].second);
}
void inorder(int x)
{
if(x>n || x == 0) return ;
inorder(a[x].first);
cout<<x<<" ";
inorder(a[x].second);
}
void postorder(int x)
{
if(x>n || x == 0) return ;
postorder(a[x].first);
postorder(a[x].second);
cout<<x<<" ";
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
a[i] = {x,y};
}
preorder(1);cout<<endl;
inorder(1);cout<<endl;
postorder(1);
return 0;
}
例题3 二叉树的最近公共祖先 (lca)
http://oj.daimayuan.top/course/7/problem/457
题目
给你一棵 n 个节点的二叉树，节点的编号为 1 到 n，二叉树的根为 1 号节点。
读入 u,v，请求出 u 号节点和 v 号节点的最近公共祖先（Lowest Common Ancestor）。
如果 x 号节点既是 u 号节点的祖先也是 v 号节点的祖先，则称 x 号节点是 u 号节点和 v 号节点的公共祖先。
如果 x 号节点是 u 号节点和 v 号节点的所有公共祖先中深度最深的，则称 x 号节点是 u 号节点和 v 号节点的最近公共祖先。
输入格式
第一行一个整数 n 表示节点数。接下来 n 行，每行两个整数，第一个整数表示 i 号节点的左儿子的编号，第二个整数表示 i 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。
输入保证是一棵二叉树。
最后一行两个整数 u,v 表示要求最近公共祖先的两个节点的编号。
输出格式
输出一行一个整数，代表 u 号节点和 v 号节点的最近公共祖先。样例输入
4
0 2
3 4
0 0
0 0
3 4
样例输出
2
数据规模
对于所有数据，保证 2≤n≤1000,1≤u,v≤n。
代码
# include<bits/stdc++.h>
using namespace std;
int p[1111];
bool st[1111];
int main()
{
int n;cin>>n;
p[1] = 1;
for(int i=1;i<=n;i++)
{
int x,y;cin>>x>>y;
p[x] = i;p[y] = i;
}
int u,v;cin>>u>>v;
while(u!=1)
{
st[u] = true;u = p[u]; //记录一个点的所有祖先
}
st[1] = true;
while(!st[v]) v = p[v]; //遍历另一个点的所有祖先，第一个和u祖先重合的就是最近公共祖先
cout<<v<<endl;
return 0;
}
例题4 二叉树子树和
http://oj.daimayuan.top/course/7/problem/459
题目
给你一棵 n 个节点的二叉树，节点的编号为 1 到 n，二叉树的根为 1 号节点。每个节点都有一个权值，i 号节点的权值为 ai，请求出每个节点的子树的权值和（子树内节点的权值的和）。
输入格式
第一行一个整数 n 表示节点数。接下来 n 行，每行两个整数，第一个整数表示 i 号节点的左儿子的编号，第二个整数表示 i 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。
输入保证是一棵二叉树。
接下来一行 n 个整数，第 i 个整数 ai 表示 i 号节点的权值。
输出格式
输出一行 n 个整数，第 i 个整数表示 i 号节点的子树的权值和。样例输入
4
2 3
0 0
4 0
0 0
1 1 1 1
样例输出
4 1 2 1
数据规模
对于所有数据，保证 1≤n≤1000000,1≤ai≤100。
这其实是一道记忆化搜索,涉及到了二叉树
代码
# include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e6+10;
pii a[N];
int ans[N];
int solve(int x)
{
int t = ans[x];
if(a[x].first) t+=solve(a[x].first);
if(a[x].second) t+=solve(a[x].second);
ans[x] = t;
return t;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;cin>>x>>y;
a[i] = {x,y};
}
for(int i=1;i<=n;i++) {int x;cin>>x;ans[i] = x;}
solve(1);
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}