• • 什么是二叉樹(shù)？
  • 二叉樹(shù)的定義
  • 二叉樹(shù)的基本形態(tài)
  • 二叉樹(shù)的性質(zhì)
  • 例題1：二叉樹(shù)的遍歷
  • • • 題目描述
      • 輸入
      • 輸出
      • 樣例
      • 代碼
  • 例題2：哈夫曼樹(shù)
  • • • 題目描述
      • 輸入
      • 輸出
      • 樣例
      • 代碼

🎆🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎆
今天我要開(kāi)啟一個(gè)新計(jì)劃----【C++天梯計(jì)劃】
目的是通過(guò)天梯計(jì)劃，通過(guò)題目和知識(shí)點(diǎn)串聯(lián)的方式，完成C++復(fù)習(xí)與鞏固。

二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分 。
二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根（root）的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)節(jié)點(diǎn) 。

二叉樹(shù)（binary tree）是指樹(shù)中節(jié)點(diǎn)的度不大于2的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱(chēng)作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù) 。

二叉樹(shù)是遞歸定義的，其節(jié)點(diǎn)有左右子樹(shù)之分，邏輯上二叉樹(shù)有五種基本形態(tài)
1、空二叉樹(shù)——如圖（1）
2、只有一個(gè)根節(jié)點(diǎn)的二叉樹(shù)——如圖（2）
3、只有左子樹(shù)——如圖（3）
4、只有右子樹(shù)——如圖（4）
5、完全二叉樹(shù)——如圖（5）

1-----------2-----------------3---------------4------------------5

性質(zhì)1： 二叉樹(shù)的第i層上至多有2i-1（i≥1）個(gè)節(jié)點(diǎn) [6] 。
性質(zhì)2： 深度為h的二叉樹(shù)中至多含有2h-1個(gè)節(jié)點(diǎn) [6] 。
性質(zhì)3： 若在任意一棵二叉樹(shù)中，有n0個(gè)葉子節(jié)點(diǎn)，有n2個(gè)度為2的節(jié)點(diǎn)，則必有n0=n2+1 [6] 。
性質(zhì)4： 具有n個(gè)節(jié)點(diǎn)的滿(mǎn)二叉樹(shù)深為log2n+1。
性質(zhì)5： 若對(duì)一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行順序編號(hào)（1≤i≤n），那么，對(duì)于編號(hào)為i（i≥1）的節(jié)點(diǎn)：
當(dāng)i=1時(shí)，該節(jié)點(diǎn)為根，它無(wú)雙親節(jié)點(diǎn)。
當(dāng)i>1時(shí)，該節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編號(hào)為i/2 。
若2i≤n，則有編號(hào)為2i的左節(jié)點(diǎn)，否則沒(méi)有左節(jié)點(diǎn)。
若2i+1≤n，則有編號(hào)為2i+1的右節(jié)點(diǎn)，否則沒(méi)有右節(jié)點(diǎn) 。

題目描述

給出一個(gè) nn 個(gè)結(jié)點(diǎn)的二叉樹(shù)，請(qǐng)求出二叉樹(shù)的前序遍歷，中序遍歷和后序遍歷。

輸入

第一行有一個(gè)整數(shù) nn (0< n ≤ 260以下 nn 行，每行第一個(gè)為一個(gè)大寫(xiě)字母表示結(jié)點(diǎn)的值，第 i+1i+1 行的結(jié)點(diǎn)編號(hào)為 ii ；
后面為兩整數(shù)，第一個(gè)表示該結(jié)點(diǎn)左孩子結(jié)點(diǎn)編號(hào)，第二個(gè)表示該結(jié)點(diǎn)右孩子的結(jié)點(diǎn)編號(hào)，如果該編號(hào)為 00 表示沒(méi)有；（編號(hào)為 11 的結(jié)點(diǎn)是樹(shù)的根）

輸出

共三行，第一行為二叉樹(shù)的前序遍歷，第二行為中序遍歷，第三行為后序遍歷；

樣例

輸入
7
F 2 3
C 4 5
E 0 6
A 0 0
D 7 0
G 0 0
B 0 0
輸出
FCADBEG
ACBDFEG
ABDCGEF

#includeusing namespace std;
//1.用孩子表示法，存儲(chǔ)二叉樹(shù)
//2.用遞歸的方法得到先序中序后序遍歷的結(jié)果 
const int N = 30;
struct node{char c;
	int lc,rc;//左右孩子 
}a[N]; 
int n;

//前序遍歷：根左右 
void dfs1(int x){cout<if(a[x].lc) dfs2(a[x].lc);
	cout<if(a[x].lc) dfs3(a[x].lc);
	if(a[x].rc) dfs3(a[x].rc);
	cout<cin>>n;
	//讀入結(jié)點(diǎn)
	for(int i = 1;i<= n;i++){cin>>a[i].c>>a[i].lc>>a[i].rc;
	} 
	
	//深搜
	//前序遍歷
	dfs1(1);	
	cout<

#includeusing namespace std;
//思路：使用優(yōu)先隊(duì)列模擬哈夫曼樹(shù)的構(gòu)建過(guò)程
//小根堆 
priority_queue,greater>q; 
int n,x,ans = 0;//ans：代表哈夫曼樹(shù)的WPL的值 
 
int main(){cin>>n;
	//讀入n個(gè)元素 
	while(n--){cin>>x;
		q.push(x);
	}
	
	//當(dāng)隊(duì)列中超過(guò)1個(gè)元素
	//獲取隊(duì)列頭部的2個(gè)最小的元素
	int a,b; 
	while(q.size() >1){a = q.top();
		q.pop();
		b = q.top();
		q.pop();
		
		ans += a + b;
		q.push(a+b);
	} 
	
	cout<