一些定義

• 先序，中序，后序遍歷中的序是遍歷根的順序

• 層序遍歷就是這個(gè)數(shù)的bfs序列

樹的存儲(chǔ)

有很多種存儲(chǔ)方式，一般用結(jié)構(gòu)體數(shù)組。
數(shù)組下標(biāo)對(duì)應(yīng)這個(gè)數(shù)的結(jié)點(diǎn)，既可以存左兒子右兄弟又可以存左兒子右兒子。
下面來看一些題真切的感受一下代碼

例題1 遍歷完全二叉樹

http://oj.daimayuan.top/course/7/problem/430

題目

給你一棵 n 個(gè)節(jié)點(diǎn)的完全二叉樹，節(jié)點(diǎn)的編號(hào)為 1 到 n，二叉樹的根為 1 號(hào)節(jié)點(diǎn)。編號(hào)為 i (1≤i≤n) 的節(jié)點(diǎn)的左兒子如果存在的話，編號(hào)為 i+i；編號(hào)為 i (1≤i≤n) 的節(jié)點(diǎn)的右兒子如果存在的話，編號(hào)為 i+i+1。

現(xiàn)在請(qǐng)你求出這棵完全二叉樹的先序、中序和后序遍歷的結(jié)果。

輸入格式
一行一個(gè)整數(shù) n。

輸出格式
輸出三行，每行 n 個(gè)數(shù)代表一種遍歷的結(jié)果。

第一行為先序遍歷的結(jié)果，第二行為中序遍歷的結(jié)果，第三行為后序遍歷的結(jié)果。

樣例輸入
7
樣例輸出
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
數(shù)據(jù)規(guī)模
對(duì)于所有數(shù)據(jù)，保證 1≤n≤1024。

代碼

highlighter- cpp

#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 個(gè)節(jié)點(diǎn)的二叉樹，節(jié)點(diǎn)的編號(hào)為 1 到 n，二叉樹的根為 1 號(hào)節(jié)點(diǎn)。請(qǐng)你求出這棵二叉樹的先序、中序和后序遍歷的結(jié)果。

輸入格式
第一行一個(gè)整數(shù) n 表示節(jié)點(diǎn)數(shù)。

接下來 n 行，每行兩個(gè)整數(shù)，第一個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的左兒子的編號(hào)，第二個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的右兒子的編號(hào)，如果某個(gè)數(shù)字為 0 表示沒有對(duì)應(yīng)的子節(jié)點(diǎn)。

輸入保證是一棵二叉樹。

輸出格式
輸出三行，每行 n 個(gè)數(shù)代表一種遍歷的結(jié)果。

第一行為先序遍歷的結(jié)果，第二行為中序遍歷的結(jié)果，第三行為后序遍歷的結(jié)果。

樣例輸入
4
2 3
0 0
4 0
0 0
樣例輸出
1 2 3 4
2 1 4 3
2 4 3 1
數(shù)據(jù)規(guī)模
對(duì)于所有數(shù)據(jù)，保證 1≤n≤1024。

代碼

highlighter- cpp

# 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 個(gè)節(jié)點(diǎn)的二叉樹，節(jié)點(diǎn)的編號(hào)為 1 到 n，二叉樹的根為 1 號(hào)節(jié)點(diǎn)。

讀入 u,v，請(qǐng)求出 u 號(hào)節(jié)點(diǎn)和 v 號(hào)節(jié)點(diǎn)的最近公共祖先（Lowest Common Ancestor）。

如果 x 號(hào)節(jié)點(diǎn)既是 u 號(hào)節(jié)點(diǎn)的祖先也是 v 號(hào)節(jié)點(diǎn)的祖先，則稱 x 號(hào)節(jié)點(diǎn)是 u 號(hào)節(jié)點(diǎn)和 v 號(hào)節(jié)點(diǎn)的公共祖先。

如果 x 號(hào)節(jié)點(diǎn)是 u 號(hào)節(jié)點(diǎn)和 v 號(hào)節(jié)點(diǎn)的所有公共祖先中深度最深的，則稱 x 號(hào)節(jié)點(diǎn)是 u 號(hào)節(jié)點(diǎn)和 v 號(hào)節(jié)點(diǎn)的最近公共祖先。

輸入格式
第一行一個(gè)整數(shù) n 表示節(jié)點(diǎn)數(shù)。

接下來 n 行，每行兩個(gè)整數(shù)，第一個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的左兒子的編號(hào)，第二個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的右兒子的編號(hào)，如果某個(gè)數(shù)字為 0 表示沒有對(duì)應(yīng)的子節(jié)點(diǎn)。

輸入保證是一棵二叉樹。

最后一行兩個(gè)整數(shù) u,v 表示要求最近公共祖先的兩個(gè)節(jié)點(diǎn)的編號(hào)。

輸出格式
輸出一行一個(gè)整數(shù)，代表 u 號(hào)節(jié)點(diǎn)和 v 號(hào)節(jié)點(diǎn)的最近公共祖先。

樣例輸入
4
0 2
3 4
0 0
0 0
3 4
樣例輸出
2
數(shù)據(jù)規(guī)模
對(duì)于所有數(shù)據(jù)，保證 2≤n≤1000,1≤u,v≤n。

代碼

highlighter- cpp

# 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];   //記錄一個(gè)點(diǎn)的所有祖先
	}
	st[1] = true;
	while(!st[v]) v = p[v];  //遍歷另一個(gè)點(diǎn)的所有祖先，第一個(gè)和u祖先重合的就是最近公共祖先
	cout<<v<<endl;
	return 0;
}

例題4 二叉樹子樹和

http://oj.daimayuan.top/course/7/problem/459

題目

給你一棵 n 個(gè)節(jié)點(diǎn)的二叉樹，節(jié)點(diǎn)的編號(hào)為 1 到 n，二叉樹的根為 1 號(hào)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)權(quán)值，i 號(hào)節(jié)點(diǎn)的權(quán)值為 ai，請(qǐng)求出每個(gè)節(jié)點(diǎn)的子樹的權(quán)值和（子樹內(nèi)節(jié)點(diǎn)的權(quán)值的和）。

輸入格式
第一行一個(gè)整數(shù) n 表示節(jié)點(diǎn)數(shù)。

接下來 n 行，每行兩個(gè)整數(shù)，第一個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的左兒子的編號(hào)，第二個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的右兒子的編號(hào)，如果某個(gè)數(shù)字為 0 表示沒有對(duì)應(yīng)的子節(jié)點(diǎn)。

輸入保證是一棵二叉樹。

接下來一行 n 個(gè)整數(shù)，第 i 個(gè)整數(shù) ai 表示 i 號(hào)節(jié)點(diǎn)的權(quán)值。

輸出格式
輸出一行 n 個(gè)整數(shù)，第 i 個(gè)整數(shù)表示 i 號(hào)節(jié)點(diǎn)的子樹的權(quán)值和。

樣例輸入
4
2 3
0 0
4 0
0 0
1 1 1 1
樣例輸出
4 1 2 1
數(shù)據(jù)規(guī)模
對(duì)于所有數(shù)據(jù)，保證 1≤n≤1000000,1≤ai≤100。

這其實(shí)是一道記憶化搜索,涉及到了二叉樹

代碼

highlighter- cpp

# 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;
}

到此這篇關(guān)于二叉樹入門和刷題詳解的文章就介紹到這了,更多相關(guān)二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論