二叉树

一些定义

  1. 先序,中序,后序遍历中的序是遍历根的顺序

  2. 层序遍历就是这个数的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;
}

热门相关:流鱼无恙   富贵不能吟   万古至尊   裙上之臣   上神来了