初識 二叉樹

目錄

  • 什么是二叉樹
    • 二叉樹的五種狀態
    • 滿二叉樹
    • 完全二叉樹
    • 二叉排序樹
    • 平衡二叉樹
  • 二叉樹的遍歷
    • 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(n106) 個結點的二叉樹。給出每個結點的兩個子結點編號(均不超過 nnn),建立一棵二叉樹(根節點的編號為 111),如果是葉子結點,則輸入 0 0

建好樹這棵二叉樹之后,依次求出它的前序、中序、后序列遍歷。

輸入格式

第一行一個整數 nnn,表示結點數。

之后 nnn 行,第 iii 行兩個整數 lllrrr,分別表示結點 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 261n26)

后面 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(n106) 個結點的二叉樹。給出每個結點的兩個子結點編號(均不超過 nnn),建立一棵二叉樹(根節點的編號為 111),如果是葉子結點,則輸入 0 0

建好這棵二叉樹之后,請求出它的深度。二叉樹的深度是指從根節點到葉子結點時,最多經過了幾層。

輸入格式

第一行一個整數 nnn,表示結點數。

之后 nnn 行,第 iii 行兩個整數 lllrrr,分別表示結點 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 之間的距離表示從 uuuvvv 的最短有向路徑上向根節點的邊數的兩倍加上向葉節點的邊數。

給定一顆以 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 1001u,v,x,yn100,且給出的是一棵樹。保證 uuuvvv 的父結點。

求深度

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

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/915335.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/915335.shtml
英文地址,請注明出處:http://en.pswp.cn/news/915335.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

(1)Windows環境下安裝Oracle

概述&#xff1a;Oracle數據庫是一種網絡上的數據庫, 它在網絡上支持多用戶, 支持服務器/客戶機等部署(或配置)。服務器與客戶機是軟件概念&#xff1a;它們與計算機硬件不存在一一對應的關系. 即:同一臺計算機既可以充當服務器又可以充當客戶機,或者一臺計算機只充當服務器或只…

工業數據集成中間件工具OPC Router詳細介紹

一、產品概述 OPC Router 是 Software Toolbox 旗下的一款面向工業數據集成與自動化的數據中間件工具&#xff0c;專注于實現各類工業系統之間的數據交互和自動化流程編排。它通過模塊化的插件機制&#xff0c;打通 PLC、ERP、MES、數據庫、MQTT、REST API 等不同系統之間的數…

消息隊列 2.RabbitMQ的基本概念與使用

RabbitMQ 是一款基于 AMQP&#xff08;Advanced Message Queuing Protocol&#xff09;協議的開源消息中間件&#xff0c;主要用于實現分布式系統中的消息傳遞&#xff0c;支持異步通信、系統解耦、流量削峰等場景。在 Java 生態中&#xff0c;RabbitMQ 被廣泛應用&#xff0c;…

【web安全】SQL注入與認證繞過

目錄 一、SQL注入漏洞 1.1 基礎注入原理 1.2 實用注入Payload分類 邏輯繞過型 注釋截斷型 聯合查詢型 常見的萬能密碼-CSDN博客 二、登錄繞過實戰技巧 2.1 基礎繞過手法 2.2 高級繞過技巧 編碼繞過 多重注釋 參數污染 三、密碼重置漏洞利用 3.1 常見漏洞模式 3…

Python適配器模式詳解:讓不兼容的接口協同工作

一、模式定義與核心思想 適配器模式&#xff08;Adapter Pattern&#xff09; 是一種結構型設計模式&#xff0c;它通過創建一個中間層&#xff08;適配器&#xff09;&#xff0c;將不兼容的接口轉換為客戶端期望的接口。就像現實中的電源適配器&#xff0c;讓不同國家的插頭…

微信小程序列表數據上拉加載,下拉刷新

1.上拉加載數據&#xff0c;數據 下一頁數據 前面的數據&#xff08;[...this.data.list, ...data.records&#xff09;2.當用戶上拉加載過快時&#xff0c;會不停的調用接口&#xff0c;需要節流閥isLoading3.上拉加載到最后一頁的判斷&#xff0c;isFinish// pages/list.js…

【樹上倍增 LCA DFS 前綴和】P10391 [藍橋杯 2024 省 A] 零食采購|普及+

本文涉及知識點 C算法&#xff1a;前綴和、前綴乘積、前綴異或的原理、源碼及測試用例 包括課程視頻 CDFS 樹上倍增 LCA P10391 [藍橋杯 2024 省 A] 零食采購 題目描述 小藍準備去星際旅行&#xff0c;出發前想在本星系采購一些零食&#xff0c;星系內有 nnn 顆星球&#x…

PDF發票批量打印工具哪個好?高效打印發票的實用工具推薦

開小超市這幾年&#xff0c;每月要打幾十張進貨發票做賬&#xff0c;以前打印時總犯愁&#xff1a;有的發票 PDF 太大&#xff0c;打出來字小得看不清&#xff1b;有的又太窄&#xff0c;白白浪費半張紙。試過手動調整&#xff0c;每張都要改縮放比例&#xff0c;累不說&#x…

4G模塊 A7680通過MQTT協議連接到華為云

命令說明 基礎AT指令 ATi顯示產品的標志信息 ATCIMI查詢IMSI ATCICCID從SIM卡讀取ICCID ATCGSN查詢產品序列號 ATCPIN查詢卡狀態 ATCSQ查詢信號強度 ATCGATT查詢當前PS域狀態 ATCREG查詢GPRS注冊狀態 ATCEREG查詢4G注冊狀態 ATCGPADDR查詢PDP地址 ATCMGF選擇短信格式 ATCMGS發…

大模型詞表設計與作用解析

幾乎所有大型語言模型&#xff08;LLM&#xff09;都有自己獨立的詞表&#xff08;Vocabulary&#xff09;。這是模型設計和訓練過程中的核心組件之一。以下是關于詞表的關鍵點&#xff1a; 1. 詞表的作用 分詞基礎&#xff1a;詞表定義了模型如何將輸入文本拆分成基本單元&…

(一)Eshop(異常處理中間件/grpc)

文章目錄項目地址一、異常處理1.1 自定異常1.2 自定義異常處理中間件1.3 注冊中間件二、grpc服務2.1 創建protos1. 打折的protos2. 設置grpc server3. program配置服務4. docker-compose2.2 CRUD1. 查詢2.3 測試1. 發起查詢請求三、grpc服務消費3.1 創建client1. 添加服務2. 選…

BLIP、InternVL Series(下)

目錄 一、InternVL1.5 1、改進 二、InternVL2 1、漸進式擴展 2、多模態擴展 三、InternVL2.5 1、方法 2、數據優化 四、InternVL3 2、方法 3、訓練后處理 4、測試時擴展 五、BLIP-3o 一、InternVL1.5 1、改進 InternVL1.5在InternVL基礎上&#xff0c;優化了QLLa…

【數據結構】二維差分數組

題目鏈接 【模板】二維差分_牛客題霸_牛客網 牛客網 - 找工作神器|筆試題庫|面試經驗|實習招聘內推&#xff0c;求職就業一站解決_牛客網 描述 給定一個 nmnm 的整數矩陣 bb&#xff0c;矩陣的下標從 11 開始記作 bi,jbi,j?。現在需要支持 qq 次操作&#xff0c;第 tt 次…

【JDK內置工具】常用工具和實戰指令

作者&#xff1a;唐叔在學習 專欄&#xff1a;唐叔的Java實踐 關鍵詞: #JDK工具 #Java性能調優 #JVM調優 #內存泄漏排查 #線程死鎖分析 #Java開發工具 #線上問題排查 #Java診斷工具 Hello&#xff0c;大家好&#xff0c;我是愛學習的唐叔。作為Java開發者&#xff0c;JDK內置工…

一站式PDF轉Markdown解決方案PDF3MD

簡介 什么是 PDF3MD &#xff1f; PDF3MD 是一個現代化、用戶友好的網絡應用程序&#xff0c;旨在將 PDF 文檔轉換為干凈、格式化的 Markdown 文本。它提供了高效的轉換工具&#xff0c;支持多種文件格式之間的轉換。 主要特點 PDF 轉 Markdown&#xff1a;能夠將 PDF 文檔轉…

RocketMQ學習系列之——MQ入門概念

一、什么是MQMQ&#xff08;Message Queue&#xff0c;消息隊列&#xff09;是一種能夠實現跨進程消息傳輸&#xff0c;并且消息緩存符合隊列特性的組件。二、MQ的作用異步&#xff1a;消息發送方無需等待消息接收方收到消息&#xff0c;發送方將消息成功發送到 MQ 之后即可無阻…

血條識別功能實現及原理

從零開始學Python圖像處理 - 血條識別 從實際問題中能快速的學習特定技能&#xff0c;通過完成一個能自動刷怪的工具&#xff0c;達成快速學習python圖像處理和識別。 自動刷怪需要先識別怪物&#xff0c;在游戲中怪物類型很多&#xff0c;同時在移動中形態會一直發生變化&…

網絡地址和主機地址之間進行轉換的類

#pragma once #include "Common.hpp" // 網絡地址和主機地址之間進行轉換的類class InetAddr { public:InetAddr(){}InetAddr(struct sockaddr_in &addr) : _addr(addr){// 網絡轉主機_port ntohs(_addr.sin_port); // 從網絡中拿到的&#xff01;網絡序列// _i…

《Python 項目 CI/CD 實戰指南:從零構建自動化部署流水線》

??《Python 項目 CI/CD 實戰指南:從零構建自動化部署流水線》 一、引言:為什么 Python 項目需要 CI/CD? 在現代軟件開發中,CI/CD(持續集成 / 持續部署)已成為不可或缺的工程實踐。它不僅提升了開發效率,還顯著降低了部署風險。對于 Python 項目而言,CI/CD 的價值尤…

AJAX 技術

AJAX全稱是 Asynchronous JavaScript and XML ( 異步的JavaScript 和 XML )&#xff0c;使用該技術后&#xff0c;可以實現不刷新整個網頁&#xff0c;與服務器進行異步通信并更新部分網頁。一&#xff09;為什么需要AJAX?傳統網頁在與服務器通信時&#xff0c;需要刷新整個頁…