樹和二叉樹_幹貨筆記
-
- 樹的定義和基本術語
- 二叉樹
- 樹和森林
- 赫夫曼樹及其應用
樹的定義和基本術語
1.樹型結構是一類非線性資料結構，樹是以分支關系定義的層次結構。
2.樹是n（n≥0）個結點的有限集。在任意一課非空樹中：
（1）有且僅有一個特定的稱為根的結點。
（2）當n>1時，其餘結點可分為m（m>0）個互不相交的有限集T1,T2,……Tm，其中每一個
集合本身又是一棵樹，并且稱為根的子樹。
3.樹的結點包含一個資料元素及若幹指向其子樹的分支。
4.度：結點擁有的子樹數稱為結點的度。
5.葉子/終端結點：度為0的結點。
6.分支結點/非終端節點：度不為0的結點。
7.樹的度：樹内各結點的度的最大值。
8.祖先：從根到該結點所經分支上的所有結點。
9.子孫：以某結點為根的子樹中任一結點。
10.深度/高度：樹中結點的最大層次。
11.有序樹：将樹中結點的各子樹看成從左至右是有次序的（即不能互換），稱該樹為有序樹
12.森林：森林是m（m≥0）棵互不相交的樹的集合。對樹中的每個結點而言，其子樹的集合
即為森林。
13.就邏輯結構而言，任何一棵樹是一個二進制組Tree=（root，F），其中：root是資料元素，
稱做樹的根節點；F是m（m≥0）棵樹的森林，F=（T1,T2,...,Tm），其中Ti=（r，Fi）稱
做根root的第i棵子樹；當m≠0時，在樹根和其子樹森林之間存在下列關系：
RF=｛<root,ri>|i=i,2,...,m,m>0｝
14.樹的邏輯結構：
（1）特點：一對多（1：n）
（2）除了根結點，其餘結點都隻有一個直接前驅，有多個直接後，且子樹之間互不相交。
15.樹的存儲結構：順序存儲、鍊式存儲
二叉樹
1.二叉樹是另一種樹形結構，它的特點是每個結點至多隻有兩棵子樹。是n（n≥0）個結點
的有限集合，由一個根結點以及兩棵互不相交的、分别稱為左子樹和右子樹的二叉樹組成 。
2.所有有序樹都能轉為唯一對應的二叉樹。
3.邏輯結構： 一對二（1：2）
4.基本特征：① 每個結點最多隻有兩棵子樹（不存在度大于2的結點）；
② 左子樹和右子樹次序不能颠倒（有序樹）。.
5.二叉樹的性質：
（1）在二叉樹的第i層至多有2^(i-1)個結點（i≥1）。
（2）深度為k的二叉樹至多有2^(k)-1個結點，（k≥1）。
（3）對任何一棵二叉樹T，如果其終端結點樹為n0，度為2的結點數為n2，則n0=n2+1。
（4）設n1為二叉樹T中度為1的結點數，由于二叉樹中所有結點的度均小于或等于2，是以
其結點總數為：n=n0+n1+n2.
（5）結點總數=分支數（B）+1； 終端結點數（n0）=（度為2結點數）n2+1。
（6）滿二叉樹：一棵深度為k且有2^(k)-1個結點的二叉樹。
滿二叉樹的特點：
① 葉子隻能出現在最下一層；
② 隻有度為0和度為2的結點。
（7）完全二叉樹：對一棵具有n個結點的二叉樹按層序編号，如果編号為i（1≤i≤n）的結點
與同樣深度的滿二叉樹中編号為i的結點在二叉樹中的位置完全相同。
（8）在滿二叉樹中，從最後一個結點開始，連續去掉任意個結點，即是一棵完全二叉樹.
（9）完全二叉樹的特點：
1️⃣葉子結點隻能出現在最下兩層，且最下層的葉子結點都集中在二叉樹的左部。
2️⃣完全二叉樹中如果有度為1的結點，隻可能有一個，且該結點隻有左孩子。
3️⃣深度為k的完全二叉樹在k-1層上一定是滿二叉樹。
（10）具有n個結點的完全二叉樹的深度為[log2N]（方括号代表取整）+1.
（11）具有n個結點的完全二叉樹的葉子結點個數為n/2個。
（11）對n個結點的完全二叉樹，若從上至下、從左至右編号，則編号為i 的結點，其左孩子
編号必為2i（2i>n無左孩子），其右孩子編号必為2i＋1 （2i＋1>n無右孩子） ；其雙親
的編号必為 [ i/2 ] （i＝1 時為根,除外）
樹和森林
1. 樹的先序周遊等價于二叉樹的先序周遊 樹的後序周遊等價于二叉樹的中序周遊。
2. 森林的先序周遊等價于二叉樹的先序周遊！森林的中序周遊等價于二叉樹的中序周遊
前序周遊樹
後序周遊樹
層序周遊樹
森林先序和中序周遊
注意
赫夫曼樹及其應用
1.路徑：由一結點到另一結點間的分支所構成。
2.路徑長度：路徑上的分支數目。
3.樹的路徑長度：從樹根到每一結點的路徑長度之和。
4.帶權路徑長度(WPL)：結點到根的路徑長度與結點上權的乘積。
5.樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和
6.哈 夫 曼 樹：帶權路徑長度最小的二叉樹
7.哈夫曼樹的特點：
(1). 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。
(2). 隻有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.
補充：
樹的基本概念
1.結點的度：結點挂起的子樹數
2.樹的度：所有結點度中的最大值。
樹的存儲結構：
3.樹的順序存儲：從上至下、從左至右将樹的結點依次存入記憶體。
重大缺陷：複原困難（不能唯一複原就沒有實用價值）。
4.樹的鍊式存儲：可用多重連結清單：一個前趨指針，n個後繼指針。
缺點：等長結構太浪費（每個結點的度不一定相同）；
不等長結構太複雜（要定義好多種結構類型）。
5.解決思路：即把一般的樹轉換為二叉樹—左孩子右兄弟的方法。研究最簡單、最有規律的二叉樹即可。
圖檔來源：XX大學授課PPT