一些定義

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

• 層序遍歷就是這個數的bfs序列

樹的存儲

有很多種存儲方式，一般用結構體數組。
數組下標對應這個數的結點，既可以存左兒子右兄弟又可以存左兒子右兒子。
下面來看一些題真切的感受一下代碼

例題1 遍歷完全二叉樹

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

題目

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

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

輸入格式
一行一個整數 n。

輸出格式
輸出三行，每行 n 個數代表一種遍歷的結果。

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

樣例輸入
7
樣例輸出
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
數據規(guī)模
對于所有數據，保證 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 個節(jié)點的二叉樹，節(jié)點的編號為 1 到 n，二叉樹的根為 1 號節(jié)點。請你求出這棵二叉樹的先序、中序和后序遍歷的結果。

輸入格式
第一行一個整數 n 表示節(jié)點數。

接下來 n 行，每行兩個整數，第一個整數表示 i 號節(jié)點的左兒子的編號，第二個整數表示 i 號節(jié)點的右兒子的編號，如果某個數字為 0 表示沒有對應的子節(jié)點。

輸入保證是一棵二叉樹。

輸出格式
輸出三行，每行 n 個數代表一種遍歷的結果。

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

樣例輸入
4
2 3
0 0
4 0
0 0
樣例輸出
1 2 3 4
2 1 4 3
2 4 3 1
數據規(guī)模
對于所有數據，保證 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 個節(jié)點的二叉樹，節(jié)點的編號為 1 到 n，二叉樹的根為 1 號節(jié)點。

讀入 u,v，請求出 u 號節(jié)點和 v 號節(jié)點的最近公共祖先（Lowest Common Ancestor）。

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

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

輸入格式
第一行一個整數 n 表示節(jié)點數。

接下來 n 行，每行兩個整數，第一個整數表示 i 號節(jié)點的左兒子的編號，第二個整數表示 i 號節(jié)點的右兒子的編號，如果某個數字為 0 表示沒有對應的子節(jié)點。

輸入保證是一棵二叉樹。

最后一行兩個整數 u,v 表示要求最近公共祖先的兩個節(jié)點的編號。

輸出格式
輸出一行一個整數，代表 u 號節(jié)點和 v 號節(jié)點的最近公共祖先。

樣例輸入
4
0 2
3 4
0 0
0 0
3 4
樣例輸出
2
數據規(guī)模
對于所有數據，保證 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];   //記錄一個點的所有祖先
	}
	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 個節(jié)點的二叉樹，節(jié)點的編號為 1 到 n，二叉樹的根為 1 號節(jié)點。每個節(jié)點都有一個權值，i 號節(jié)點的權值為 ai，請求出每個節(jié)點的子樹的權值和（子樹內節(jié)點的權值的和）。

輸入格式
第一行一個整數 n 表示節(jié)點數。

接下來 n 行，每行兩個整數，第一個整數表示 i 號節(jié)點的左兒子的編號，第二個整數表示 i 號節(jié)點的右兒子的編號，如果某個數字為 0 表示沒有對應的子節(jié)點。

輸入保證是一棵二叉樹。

接下來一行 n 個整數，第 i 個整數 ai 表示 i 號節(jié)點的權值。

輸出格式
輸出一行 n 個整數，第 i 個整數表示 i 號節(jié)點的子樹的權值和。

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

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

代碼

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

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

最新評論