目錄
- 樹
- 什么是二叉樹
- 二叉樹的五種狀態
- 滿二叉樹
- 完全二叉樹
- 二叉排序樹
- 平衡二叉樹
- 二叉樹的遍歷
- B3642 二叉樹的遍歷
- P1305 新二叉樹
- 二叉樹的深度
- P4913 【深基16.例3】二叉樹深度
- 相關例題訓練:
- 二叉樹問題
樹
這是樹(拍攝于鄭州輕工業大學,第一次鄭州輕工業新生賽~)
這是樹的一些概念:
什么是二叉樹
???
二叉樹是n(n>=0)個節點的有限集合。
- 1.每個節點最多只有兩個子樹
- 2.左右子樹不能顛倒
(二叉樹是有序樹)
二叉樹的五種狀態
幾種特殊的二叉樹:
滿二叉樹
高度為h,且含有2h2^h2h-1個結點的二叉樹
特點:
- 1.只有最后一層有葉子結點
- 2.不存在度為一的點
- 3.按層序從1開始編號結點i的左孩子為2i,右孩子為2i+1
完全二叉樹
當且僅當其每個結點都與高度為h的滿二叉樹中編號問為1~n的結點一 一對應時成為完全二叉樹。
特點
- 1.只有最后兩層可能有葉子結點。
- 2.最多 只有一個度為1的結點。
- 3.按層序從1開始編號結點i的左孩子為2i,右孩子為2i+1
二叉排序樹
左子樹上所有結點的關鍵字均小于根節點的關鍵字
右子樹上所有結點的關鍵字均大于根節點的關鍵字
左子樹和右子樹又分別時一顆二叉排序樹
平衡二叉樹
樹上任一結點的左子樹和右子樹的深度之差不超過1
(有更高的搜索效率)
二叉樹的遍歷
前序遍歷
中序遍歷
后序遍歷
關于遍歷二叉樹,有一個巧妙的方法分享給大家。
以下圖為例:
以中序遍歷:左根右 為例:
我們可以先遍歷最上邊的ABC, 并給B和C的子節點留上位置
_ B
_ A
_ C
_
然后再將B和C的子節點按左根右的順序填上去
就是這個順序:DBEAFCG
同理,你可以練習一下:
先序遍歷:ABDECFG
后序遍歷:DEBFGCA
有了以上的基礎,我們拿道題練練手吧!
B3642 二叉樹的遍歷
B3642 二叉樹的遍歷
題目描述
有一個 n(n≤106)n(n \le 10^6)n(n≤106) 個結點的二叉樹。給出每個結點的兩個子結點編號(均不超過 nnn),建立一棵二叉樹(根節點的編號為 111),如果是葉子結點,則輸入 0 0
。
建好樹這棵二叉樹之后,依次求出它的前序、中序、后序列遍歷。
輸入格式
第一行一個整數 nnn,表示結點數。
之后 nnn 行,第 iii 行兩個整數 lll、rrr,分別表示結點 iii 的左右子結點編號。若 l=0l=0l=0 則表示無左子結點,r=0r=0r=0 同理。
輸出格式
輸出三行,每行 nnn 個數字,用空格隔開。
第一行是這個二叉樹的前序遍歷。
第二行是這個二叉樹的中序遍歷。
第三行是這個二叉樹的后序遍歷。
輸入 #1
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0
輸出 #1
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1
這是一道很模板的二叉樹遍歷練習題,很適合新手寶寶體質,按順序根據前序中序和后續的遍歷順序,結合深搜就可以很容易的輸出順序啦~代碼注釋很詳細!
AC代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,l[N],r[N];//l和r分別存左子節點和右子節點
//前序遍歷,根左右
void a(int x)//前序遍歷訪問到第x號點
{if(x==0)return ;//題目中說這個結點為0時表示無此結點//然后就是按照前序遍歷cout<<x<<" ";//先輸出根a(l[x]);//再輸出左子結點a(r[x]);//最后輸出右子節點
}
//中序遍歷,左根右
void b(int x)//中序遍歷訪問到第x號點
{if(x==0)return ;//中序遍歷 b(l[x]);//先輸出左子結點cout<<x<<" ";//再輸出根b(r[x]);//最后輸出右子節點
}
//后序遍歷,左右根
void c(int x)//后序遍歷訪問到第x號點
{if(x==0)return ;//后序遍歷順序 c(l[x]);//先輸出左子結點c(r[x]);//再輸出右子節點 cout<<x<<" ";//最后輸出根
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>l[i]>>r[i];//輸入對應位置的左右節點 //前序遍歷,根左右 a(1);//根節點從1開始遍歷cout<<endl;//前序遍歷完后要輸出換行//中序遍歷,左根右b(1);//根節點也是從1開始中序遍歷cout<<endl;//后序遍歷,左右根c(1);cout<<endl; return 0;
}
再來一道例題練練手吧!
P1305 新二叉樹
P1305 新二叉樹
題目描述
輸入一串二叉樹,輸出其前序遍歷。
輸入格式
第一行為二叉樹的節點數 nnn。(1≤n≤261 \leq n \leq 261≤n≤26)
后面 nnn 行,每一個字母為節點,后兩個字母分別為其左右兒子。特別地,數據保證第一行讀入的節點必為根節點。
空節點用 *
表示
輸出格式
二叉樹的前序遍歷。
輸入 #1
6
abc
bdi
cj*
d**
i**
j**
輸出 #1
abdicj
一道很基礎的二叉樹題,可以通過結構體將這個二叉樹建立起來,雖然題目中給的字符,但同樣可以存儲在結構體數組中,因為字符ACS碼最大不超過128,所以數組只需開150就足夠,然后可以利用深搜,將第一個節點傳入dfs,依次搜索,當子節點不為 * 時才繼續往下搜。
AC代碼
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
struct node//簡單的建樹
{char l,r;
}p[150];
int n;
void dfs(char bg)
{cout<<bg;if(p[bg].l !='*') dfs(p[bg].l);//如果不為空節點就接著往下搜 if(p[bg].r !='*') dfs(p[bg].r);
}
void solve()
{cin>>n;char a,x,y,bg;cin>>a>>x>>y;bg=a;//作為初始深搜的點 p[a].l =x,p[a].r =y;//左右子數 n-=1;while(n--){cin>>a>>x>>y;p[a].l =x,p[a].r =y;}dfs(bg);
}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}
二叉樹的深度
二叉樹深度簡而言之就是這個二叉樹最多有幾層
比如這個二叉樹,它的深度就是3
我們直接上例題感受一下吧!
P4913 【深基16.例3】二叉樹深度
題目描述
有一個 n(n≤106)n(n \le 10^6)n(n≤106) 個結點的二叉樹。給出每個結點的兩個子結點編號(均不超過 nnn),建立一棵二叉樹(根節點的編號為 111),如果是葉子結點,則輸入 0 0
。
建好這棵二叉樹之后,請求出它的深度。二叉樹的深度是指從根節點到葉子結點時,最多經過了幾層。
輸入格式
第一行一個整數 nnn,表示結點數。
之后 nnn 行,第 iii 行兩個整數 lll、rrr,分別表示結點 iii 的左右子結點編號。若 l=0l=0l=0 則表示無左子結點,r=0r=0r=0 同理。
輸出格式
一個整數,表示最大結點深度。
輸入 #1
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
輸出 #1
4
思路分析
我們可以先利用結構體讀入這個二叉樹
- 擁有左子節點和右子節點兩個參數的結構體
- 開n范圍的結構體數組
搜索(dfs)
- 狀態:當前走到什么編號的節點以及當前的深度
- 終止條件:走到0號節點(更新最大深度)
- 走到哪里去?當前所在編號的節點的左右子節點
輸出最大深度
AC代碼
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
struct node//建樹
{int l,r;
}p[N];
int n,ans=INT_MIN;//ans用來記錄樹的最大深度
void dfs(int x,int h)
{//終止條件:子節點為0時 ans=max(ans,h);//更新最大值 //走到哪里去if(p[x].l)//如果左子節點不為0 dfs(p[x].l,h+1);if(p[x].r)//如果右子節點不為0 dfs(p[x].r,h+1);
}
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i].l>>p[i].r;dfs(1,1);//傳入最初所在位置和最初深度cout<<ans;
}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}
相關例題訓練:
二叉樹問題
P3884 [JLOI2009] 二叉樹問題
題目描述
如下圖所示的一棵二叉樹的深度、寬度及結點間距離分別為:
- 深度:444
- 寬度:444
- 結點 8 和 6 之間的距離:888
- 結點 7 和 6 之間的距離:333
其中寬度表示二叉樹上同一層最多的結點個數,節點 u,vu, vu,v 之間的距離表示從 uuu 到 vvv 的最短有向路徑上向根節點的邊數的兩倍加上向葉節點的邊數。
給定一顆以 1 號結點為根的二叉樹,請求出其深度、寬度和兩個指定節點 x,yx, yx,y 之間的距離。
輸入格式
第一行是一個整數,表示樹的結點個數 nnn。
接下來 n?1n - 1n?1 行,每行兩個整數 u,vu, vu,v,表示樹上存在一條連接 u,vu, vu,v 的邊。
最后一行有兩個整數 x,yx, yx,y,表示求 x,yx, yx,y 之間的距離。
輸出格式
輸出三行,每行一個整數,依次表示二叉樹的深度、寬度和 x,yx, yx,y 之間的距離。
輸入 #1
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
輸出 #1
4
4
8
說明/提示
對于全部的測試點,保證 1≤u,v,x,y≤n≤1001 \leq u, v, x, y \leq n \leq 1001≤u,v,x,y≤n≤100,且給出的是一棵樹。保證 uuu 是 vvv 的父結點。
求深度
- 1.構建樹,用結構體更方便
- 2.dfs對每個節點深度賦值
- 3.找到所有節點深度最大值
求寬度
- 1.統計每一層的寬度
- 2.求寬度最大值
求距離
BFS
AC代碼
#include<bits/stdc++.h>
using namespace std;
struct node//建樹
{int l,r,f,d;//分別代表左子節點、右子節點、父節點和當前節點深度
}ns[105];
struct node2//便于查找距離
{int pos,step;
};
int dp=0,wd,wid[105],st[105];//分別表示當前最大深度、寬度,寬度數組和狀態數組
void dfs(int p)
{if(st[p])return ;//如果已經被訪問過return st[p]=1;//標記為1 int le=ns[p].l ,ri=ns[p].r ,de=ns[p].d;//左子節點右子節點深度賦值 dp=max(dp,de);//更新最大深度 wid[de]++;//記錄寬度 if(le)//如果有左子節點 {ns[le].d=de+1;//深度加1 dfs(le);//接著向下搜 }if(ri)//如果有右子節點 {ns[ri].d =de+1;dfs(ri);}
}
int main()
{int n,u,v,x,y;cin>>n;for(int i=1;i<n;i++)//n-1條邊 {cin>>u>>v;if(!ns[u].l) ns[u].l =v;//如果沒有左子節點存入左子節點 else ns[u].r =v;//否則存入右子節點 ns[v].f=u;//記得更新父節點 }cin>>x>>y;//輸入要查找距離的兩個點 ns[1].d =1; //第一個節點即初始深度為1 dfs(1);//傳入當前位置節點 for(int i=1;i<=n;i++)//循環遍歷找出最大寬度 wd=max(wd,wid[i]);cout<<dp<<endl<<wd<<endl;//輸出最大深度和最大寬度 memset(st,0,sizeof(st));//將狀態數組重置為0 node2 tn={x,0};//將初始點和距離值傳入 st[x]=1;//狀態改變表示已被訪問過 queue<node2>q;//建立結構體狀態數組 q.push(tn);//將初始狀態傳進去 while(!q.empty())//當隊列不空時 {tn=q.front();//取隊首元素 q.pop();//隊首彈出 if(tn.pos==y)//當所查找的值到達y時 {cout<<tn.step;//輸出距離 break;//查找結束 }int le=ns[tn.pos].l;int ri=ns[tn.pos].r;int fa=ns[tn.pos].f;int step=tn.step ;if(le&&!st[le])//如果左子節點不空并且沒被訪問過 {st[le]=1;//更新狀態數組 q.push({le,step+1});//將更新后的位置和距離壓入隊列 }if(ri&&!st[ri])//以下同理 {st[ri]=1;q.push({ri,step+1});}if(fa&&!st[fa]){st[fa]=1;q.push({fa,step+2});//因為到父節點是向上走,所以每次更新兩步 }} return 0;
}