1.樹(Tree):
樹是 n(n>=0) 個(gè)結(jié)點(diǎn)的有限集。
當(dāng) n=0 時(shí)稱為空樹。在任意一顆非空樹中：有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)
當(dāng) n>1 時(shí)，其余結(jié)點(diǎn)可以分為 m(m>0) 個(gè)互不相交的有限集 T1,T2,..,Tm, 其中每一個(gè)集合本身又是一顆樹，并且稱為根的子樹(SubTree)
樹的分類結(jié)構(gòu)圖
┌ 普通樹 ┌ 斜樹(左斜樹、右斜樹)
│ │
┌ 樹1 ┤ 二叉樹(BinaryTree) ┤ 滿二叉樹：樹深 log(n+1)
│ │ │
│ │ └ 完全二叉樹(重要)： 樹深 [logn]+1
│ └ ...
│
森林 ─┤ 樹2
│ ...
│
└
本質(zhì)：是一對(duì)多的數(shù)據(jù)結(jié)構(gòu)
(1)結(jié)點(diǎn)分類
結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)稱為該結(jié)點(diǎn)的度(Degree)。
葉結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)
分支結(jié)點(diǎn)(非終端結(jié)點(diǎn)，內(nèi)部結(jié)點(diǎn)): 度不為 0 的結(jié)點(diǎn)
樹的度：指該樹中各結(jié)點(diǎn)的度的最大值稱為該樹的度。
(2)結(jié)點(diǎn)的關(guān)系
孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子(Child)
雙親：該結(jié)點(diǎn)稱為其孩子的雙親(Parent)
(3)結(jié)點(diǎn)的層次（這個(gè)層次的概念是針對(duì)結(jié)點(diǎn)而言的）
從根開始定義起，根為第一層，根的孩子為第二層。
(4)樹的深度(高度)
樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Deep),很顯然，該結(jié)點(diǎn)肯定是樹的根結(jié)點(diǎn)了。
注意：樹的深度和樹的度是不同的概念
(5)有序樹和無序樹
樹中個(gè)結(jié)點(diǎn)的子樹從左至右(或從右至左)是有序的，不能互換，則稱該樹為有序樹，否則為無序樹
(6)森林
是 m(m>=0)棵互不相交的樹的集合
2.樹的存儲(chǔ)結(jié)構(gòu)
這里已經(jīng)不能單純的采用前面的順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)，介紹三種存儲(chǔ)方式：雙親表示法、孩子表示法、孩子兄弟表示法
(1)雙親表示法(以父結(jié)點(diǎn)的角度)
用一組連續(xù)的空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每一個(gè)結(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示雙親結(jié)點(diǎn)在數(shù)組中的位置。
┌────────┬────────┐
│ data │ parent │
└────────┴────────┘
'結(jié)點(diǎn)描述'
public class PNode<T> {
public int parent; //父結(jié)點(diǎn)的位置
public T data; //數(shù)據(jù)域
}
(2)孩子表示法(以孩子結(jié)點(diǎn)的角度)
將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，以單鏈表的形式作為存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果是葉子結(jié)點(diǎn)則此單鏈表為空，然后n個(gè)頭指針又組成一個(gè)線性表，采用順序存儲(chǔ)結(jié)構(gòu)，存放入一個(gè)一維數(shù)組中。
1 A -> 1 -> 2
2 B -> 3
3 C -> 4 -> 5
4 D -> 6 -> 7 -> 8
5 E -> 9
6 F
為此要使用兩種結(jié)點(diǎn)結(jié)構(gòu)：
(1)表頭結(jié)點(diǎn)
┌────┬──────────┐
│data│firstchild│
└────┴──────────┘
(2)孩子結(jié)點(diǎn)
┌─────┬────┐
│child│next│
└─────┴────┘
優(yōu)點(diǎn)：方便查找某個(gè)結(jié)點(diǎn)的兄弟，只需要遍歷相關(guān)結(jié)點(diǎn)的孩子鏈表即可。遍歷整顆樹也是很方便，循環(huán)輸出整個(gè)頭結(jié)點(diǎn)數(shù)組即可
#######(3)孩子兄弟表示法(以結(jié)點(diǎn)的兄弟為角度)
優(yōu)點(diǎn)是將一顆復(fù)雜的樹變成了一顆二叉樹
┌────┬──────────┬──────────┐
│data│firstchild│rightchild│
└────┴──────────┴──────────┘
'代碼描述'
(1)樹的結(jié)點(diǎn)描述
public class TreeNode<T> {
public TreeNode<T> lChild; //左孩子
public TreeNode<T> rChild; //右孩子
private T data; //數(shù)據(jù)域
//結(jié)點(diǎn)初始化
public TreeNode() {
data = null;
lChild = null;
rChild = null;
}
public TreeNode(T x) {
data = x;
lChild = null;
rChild = null;
}
}
'樹的數(shù)據(jù)類型定義'
public class Tree {
//其他的一些操作
...
}
3.二叉樹(Binary Tree)
是一種特殊的樹。(普通樹是可以和二叉樹相互轉(zhuǎn)換)
定義：是 n(n>=0) 個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹),或者有一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。
(1)二叉樹的特點(diǎn)
1)由于每個(gè)結(jié)點(diǎn)最多有兩棵子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)；側(cè)面也證明了，二叉樹的度 <= 2
2)左子樹和右子樹是有順序的，不可以顛倒
3)即使二叉樹中某個(gè)結(jié)點(diǎn)只有一棵子樹，也要區(qū)分是左子樹還是右子樹。
(2)特殊的二叉樹
① 斜樹：所有結(jié)點(diǎn)都只有左子樹或都只有右子樹。分別稱為左斜樹、右斜樹
② 滿二叉樹(有2個(gè)條件)：所有的分支結(jié)點(diǎn)都有左子樹和右子樹，且所有的葉子結(jié)點(diǎn)在同一層上。
**滿二叉樹的特點(diǎn): **
- 葉子結(jié)點(diǎn)只能出現(xiàn)在最下層
- 非葉子結(jié)點(diǎn)的度均為 2
- 在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多，葉子結(jié)點(diǎn)最多
③ 完全二叉樹：如果編號(hào)為 i(1<= i <= n) 的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為 i 的結(jié)點(diǎn)在二叉樹中的位置完全相同，則稱為完全二叉樹。
完全二叉樹的特點(diǎn):
1)樹的編號(hào)是連續(xù)的
2)葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層
3)最下層的葉子結(jié)點(diǎn)一定集中在左部連續(xù)的位置
(3)二叉樹的性質(zhì)(理解記憶)
1)在二叉樹的第 i 層上至多有 2^(i-1)個(gè)結(jié)點(diǎn)
2)深度為k的二叉樹至多有 2^k-1 個(gè)結(jié)點(diǎn)(k >= 1)
注：當(dāng)為滿二叉樹的時(shí)候，結(jié)點(diǎn)個(gè)數(shù)為：2^k-1
3)對(duì)任何一顆二叉樹T, 如果其終端結(jié)點(diǎn)(即葉子結(jié)點(diǎn))數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為 n2，則有 n0=n2+1;
4)具有 n 個(gè)結(jié)點(diǎn)的滿二叉樹的深度為: ** log(n+1)**
5)具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為: ** [logn]+1**
注意：這是針對(duì)于完全二叉樹，不是滿二叉樹
推導(dǎo)過程：
由于深度為 k 的滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)：n = 2^k-1
所以，深度為 k 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)：n, 滿足：
2^(k-1)-1 < n <= 2^k-1
由于n是整數(shù)，因此
——> 2^(k-1) - 1 < n < 2^k
——> 2^(k-1) <= n < 2^k
—— k-1 < logn <= k
由于k取整數(shù) ——> k = [logn]+1
6)如果對(duì)一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(易知其深度[logn]+1)，將其結(jié)點(diǎn)按層編號(hào)(從第1層到[logn]+1)層，從左到右)，對(duì)任意結(jié)點(diǎn) i (i<= i <= n)有：
ⅰ) i = 1, 則i為根結(jié)點(diǎn)，無雙親，如果i>1, 則其雙親結(jié)點(diǎn)編號(hào)：[i/2]
ⅱ) 如果 2i>n, 則結(jié)點(diǎn) i 無左孩子（且i為葉子結(jié)點(diǎn)）；否則其左孩子編號(hào)：2i
ⅲ) 如果 2i+1>n, 則無右孩子；否則右孩子的編號(hào)：2i+1
(4)二叉樹的存儲(chǔ)
存儲(chǔ)方式和普通樹的存儲(chǔ)方式還是有很大的差別，尤其是它可以實(shí)現(xiàn)順序存儲(chǔ)
1)順序存儲(chǔ)結(jié)構(gòu)
用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置是可以反映出各個(gè)結(jié)點(diǎn)之間的邏輯關(guān)系。（這點(diǎn)是不同于普通樹）
對(duì)于"完全二叉樹"而言：
┌───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │
└───┴───┴───┴───┴───┴───┴───┘
對(duì)于"普通的二叉樹"可以當(dāng)成完全二叉樹來存儲(chǔ)，只是把沒有結(jié)點(diǎn)的地方設(shè)為"^"
┌───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ ^ │ E │ ^ │ G │
└───┴───┴───┴───┴───┴───┴───┘
對(duì)于"斜二叉樹"而言就有些浪費(fèi)了空間，因此，這種順序存儲(chǔ)結(jié)構(gòu)比較適合"完全二叉樹"
2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
由于二叉樹的每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子，因此，其結(jié)點(diǎn)可以設(shè)計(jì)成如下形式:
┌────────┬─────┬────────┐
│ lChild │ data│ rChild │
└────────┴─────┴────────┘
'代碼描述'
public class BinTreNode<T> {
T data; //數(shù)據(jù)域
BinTreNode<T> lChild; //左孩子結(jié)點(diǎn)指針
BinTreNode<T> rChild; //右孩子節(jié)點(diǎn)指針
public BinTreNode() {
this.data = null;
this.lChild = null;
this.rChild = null;
}
public BinTreNode(T x) {
this.data = x;
this.lChild = null;
this.rChild = null;
}
}
注意：如果為了方便找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，就同普通樹中處理方式一樣，增加一個(gè)指向其雙親結(jié)點(diǎn) parent 的指針域即可：
┌──────┬────┬──────┬──────┐
│lChild│data│rChild│parent│
└──────┴────┴──────┴──────┘
(5)遍歷二叉樹(Traversing binary Tree)
含義：是指從根結(jié)點(diǎn)出發(fā)，按照某種"次序"依次"訪問"二叉樹的所有結(jié)點(diǎn)并且只被訪問一次。
二叉樹的遍歷不同于線性數(shù)據(jù)結(jié)構(gòu)：
因?yàn)榫€性數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)都是有唯一的前驅(qū)或后繼結(jié)點(diǎn)，這使得遍歷結(jié)果是唯一確定；
然而，在二叉樹(普通樹也是如此)中每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)不唯一，可以有多種選擇，因此選擇
不同，遍歷結(jié)果也就不同了。
二叉樹：
A
╱ ╲
B C
╱ ╱ ╲
D E F
╱ ╲ ╲
G H I
二叉樹常見的遍歷方式：
1)前序遍歷: ABDGHCEIF
規(guī)則：若二叉樹為空，則遍歷結(jié)果返回空。否則先訪問根結(jié)點(diǎn)、左子樹、右子樹。
2)中序遍歷: GDHBAEICF
規(guī)則：若二叉樹為空，則遍歷結(jié)果返回空。否則先從根結(jié)點(diǎn)開始(不是訪問根結(jié)點(diǎn))，中序遍歷根結(jié)點(diǎn)的左子樹、根結(jié)點(diǎn)、右子樹
3)后序遍歷: GHDBIEFCA
規(guī)則：若二叉樹為空，則遍歷結(jié)果返回空。否則先從根結(jié)點(diǎn)開始(不是訪問根結(jié)點(diǎn))，后序遍歷根結(jié)點(diǎn)的左子樹、右子樹、根結(jié)點(diǎn)。
4)層序遍歷(層次遍歷)：ABCDEFGHI
規(guī)則：若二叉樹為空，則遍歷結(jié)果返回空。否則從樹的根結(jié)點(diǎn)開始遍歷，從上至下，逐層遍歷訪問
**注意: **
1.前、中、后遍歷方式，是針對(duì)"根結(jié)點(diǎn)"來說的
2.為什么要研究遍歷?
因?yàn)橛?jì)算機(jī)只會(huì)處理線性序列，因此，我們需要研究如何把樹這種非線性序列轉(zhuǎn)變?yōu)榫€性序列。
3.已知前序遍歷序列和中序遍歷序列，可以唯一的確定一顆二叉樹
已知后序遍歷序列和中序遍歷序列，可以唯一的確定一顆二叉樹
但是，已知前序和后序遍歷序列，無法唯一的確定一顆二叉樹
'遍歷代碼描述'：采用遞歸的方式很容易的完成
/**
* 二叉樹的遍歷方式
*/
//前序遍歷
public void preOrder(BinaTreNode<T> node) {
if (node == null) {
return ;
}
//打印根結(jié)點(diǎn)
System.out.print(node.data);
preOrder(node.lChild);
preOrder(node.rChild);
}
//中序遍歷
public void inOrder(BinaTreNode<T> node) {
if (node == null) {
return ;
}
inOrder(node.lChild);
//打印根結(jié)點(diǎn)
System.out.print(node.data);
inOrder(node.rChild);
}
//后序遍歷
public void postOrder(BinaTreNode<T> node) {
if (node == null) {
return ;
}
postOrder(node.lChild);
postOrder(node.rChild);
//打印根結(jié)點(diǎn)
System.out.print(node.data);
}
//層序遍歷：使用隊(duì)列來實(shí)現(xiàn)層序遍歷
public void levelOrder() {
BinaTreNode<T>[] queue = new BinaTreNode[this.maxNodes];
int front = -1; //隊(duì)首指針
int rear = 0; //隊(duì)尾指針
if (this.root == null) {
return;
}
queue[rear] = this.root;//二叉樹的根結(jié)點(diǎn)進(jìn)隊(duì)
//若隊(duì)不為空，則繼續(xù)遍歷
while(rear != front) {
front ++;
//打印根結(jié)點(diǎn)
System.out.print(queue[front].data);
//將隊(duì)首結(jié)點(diǎn)的左孩子進(jìn)隊(duì)
if (queue[front].lChild != null) {
rear ++;
queue[rear] = queue[front].lChild;
}
//將隊(duì)首的右孩子也進(jìn)隊(duì)
if (queue[front].rChild != null) {
rear ++;
queue[rear] = queue[front].rChild;
}
}
}
4.線索二叉樹(Thread BinaryTree)
要是能知道二叉樹每一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)或后驅(qū)結(jié)點(diǎn)是誰，將會(huì)為二叉樹的其他操作帶來方便。但是，二叉樹在存儲(chǔ)結(jié)點(diǎn)的時(shí)候，并沒有反映出來每一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)或后驅(qū)結(jié)點(diǎn)是誰。只能在二叉樹的某種遍歷過程中動(dòng)態(tài)的得到這些信息。
一個(gè)具有 n 個(gè)結(jié)點(diǎn)的二叉樹，對(duì)于其二叉鏈表存儲(chǔ)，一共有 2n 個(gè)指針域(每個(gè)結(jié)點(diǎn)有左右兩個(gè)孩子指針域)，n-1 個(gè)分支線(即兩個(gè)結(jié)點(diǎn)之間連接線)，因此，還有 2n-(n-1)=n+1 個(gè)指針域是空的，白白的浪費(fèi)，沒有利用。因此，可以考慮使用這些空閑的指針域：
將某個(gè)結(jié)點(diǎn)空閑的左指針域(lChild) 用來存儲(chǔ)該結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)結(jié)點(diǎn)
將某個(gè)結(jié)點(diǎn)空閑的右指針域(rChild) 用來存儲(chǔ)該結(jié)點(diǎn)在某種遍歷下的直接后繼結(jié)點(diǎn)
我們將這種指向前驅(qū)和后繼的指針稱為線索(Thread),加了線索的二叉樹稱為線索二叉樹
線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)：
┌────────┬────────┬──────┬────────┬────────┐
│ ltag │ lChild │ data │ rChild │ rtag │
└────────┴────────┴──────┴────────┴────────┘
ltag, rtal 是兩個(gè)標(biāo)志位(各只占了 1bit 空間)，分別用來表 lChild 和 rChild 是表示左(右)孩子結(jié)點(diǎn)還是前驅(qū)(后繼)結(jié)點(diǎn)。
┌ 0, 表示左孩子指針
ltag = │
└ 1, 表示前驅(qū)結(jié)點(diǎn)指針
┌ 0, 表示右孩子指針
rtag = │
└ 1, 表示后繼結(jié)點(diǎn)指針
線索二叉樹因遍歷順序不同，獲得的線索二叉樹也不同：
前序線索二叉樹
中序線索二叉樹
后序線索二叉樹
'結(jié)點(diǎn)代碼描述'
/**
* 線索二叉樹的結(jié)點(diǎn)
* @author Administrator
*
*/
public class ThreadedTreNode<T> {
public T data; //數(shù)據(jù)域
public ThreadedTreNode<T> lChild; //左指針域
public ThreadedTreNode<T> rChild; //右指針域
//左標(biāo)志位, 這是為了后面代碼方便才寫成boolean類型的
public boolean ltag; //true表示為前驅(qū)結(jié)點(diǎn)指針
//右標(biāo)志位, 這是為了后面代碼方便才寫成boolean類型的
public boolean rtag; //true表示后繼結(jié)點(diǎn)指針
public ThreadedTreNode() {
data = null;
lChild = null;
rChild = null;
ltag = false; //默認(rèn)表示左右孩子
rtag = false;
}
public ThreadedTreNode(T x) {
data = x;
lChild = null;
rChild = null;
ltag = false;
rtag = false;
}
}
'線索二叉樹代碼描述'
/**
* 線索二叉樹
* @author Administrator
*
*/
public class ThreadedTree<T> {
/**
* 頭結(jié)點(diǎn)，只是為了方便操作而增設(shè)的.
* 其結(jié)構(gòu)與其他線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)一樣，只是數(shù)據(jù)域不存放信息，其
* 左指針指向二叉樹的根結(jié)點(diǎn)，右指針指向自己。
* 而原二叉樹在某種遍歷下的第一個(gè)結(jié)點(diǎn)的前驅(qū)線索和最后一個(gè)結(jié)點(diǎn)的后繼線索
* 都指向該頭結(jié)點(diǎn)
*/
private ThreadedTreNode<T> head; //
private ThreadedTreNode<T> pre; //表示剛剛訪問過的結(jié)點(diǎn)
//創(chuàng)建一棵包含頭結(jié)點(diǎn)的線索二叉樹
public ThreadedTree() {
this.head = new ThreadedTreNode<T>();
}
/**
* 通過中序遍歷的序列對(duì)二叉樹進(jìn)行線索化
* @return
*/
public boolean startInThreading() {
if(head == null) {
return false;
}
//設(shè)置head結(jié)點(diǎn)為頭結(jié)點(diǎn)，其左子結(jié)點(diǎn)指向根結(jié)點(diǎn)
head.ltag = false;
head.rtag = true;
head.rChild = head; //頭結(jié)點(diǎn)的右指針指向自身。
if(head.lChild == null) {
//若二叉樹為空，則左指針指向自身
head.lChild = head;
} else {
//pre始終指向剛剛訪問過的結(jié)點(diǎn)。
pre = head; //設(shè)置默認(rèn)的前驅(qū)結(jié)點(diǎn)
inThreading(head); //按中序遍歷進(jìn)行中序線索化
//對(duì)最后一個(gè)結(jié)點(diǎn)線索化
pre.rChild = head;
pre.rtag = true;
}
return true;
}
//中序完成二叉樹線索化
private void inThreading(ThreadedTreNode<T> p) {
//p表示指向當(dāng)前結(jié)點(diǎn)
if(p == null) {
return;
}
inThreading(p.lChild); //左子樹線索化
if(p.lChild == null) {
//表明當(dāng)前結(jié)點(diǎn)的沒有左孩子(左指針域?yàn)榭?，因此，該結(jié)點(diǎn)是有前驅(qū)結(jié)點(diǎn)的。
// 此時(shí)，其前驅(qū)結(jié)點(diǎn) pre 剛剛被訪問過
//線索化
p.ltag = true; //表明左指針是前驅(qū)結(jié)點(diǎn)指針
p.lChild = pre;
}
// 由于此時(shí)p結(jié)點(diǎn)的后繼還沒有被訪問到，只能對(duì)他的前驅(qū)結(jié)點(diǎn)pre的右指針進(jìn)行判斷
if(pre.rChild == null) {
//表明 p 是 pre 的后繼
pre.rtag = true;
pre.rChild = p;
}
pre = p; //保持 pre 指向 p 的前驅(qū)
inThreading(p.rChild); //右子樹線索化
}
//遍歷二叉線索樹
public void traversing() {
ThreadedTreNode<T> node = head.lChild;
if(node == null) {
return;
}
while(!node.ltag) {
//尋找中序序列的首結(jié)點(diǎn)
node = node.lChild;
do {
if (node != null) {
System.out.println(node.data);
node = searchPostNode(node);
}
} while (node.rChild != head);
}
}
/**
* 尋找中序的后繼結(jié)點(diǎn)
* @param node
* @return
*/
public ThreadedTreNode<T> searchPostNode(ThreadedTreNode<T> node) {
ThreadedTreNode<T> q = node.rChild;
if (!node.rtag) {
while(!q.rtag) {
q = q.lChild;
}
}
return q;
}
/**
* 尋找中序的前繼結(jié)點(diǎn)
* @param node
* @return
*/
public ThreadedTreNode<T> searchPreNode(ThreadedTreNode<T> node) {
ThreadedTreNode<T> q = node.lChild;
if (!node.ltag) {
while(!q.ltag) {
q = q.rChild;
}
}
return q;
}
}
5.普通樹、森林、二叉樹之間的轉(zhuǎn)換
(1)轉(zhuǎn)換
1)樹 ——> 二叉樹
步驟：1) 在所有的兄弟之間加一條連線
2) 對(duì)樹中每一個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子的連線，刪除與其他孩子的連線
3) 層次調(diào)整。簡單的理解：想像用手捏住根結(jié)點(diǎn)往起來一提溜，靠重力下垂，
便可得到調(diào)整后的層次
2)森林 ——> 二叉樹
步驟：1) 把每個(gè)樹轉(zhuǎn)換為二叉樹
2) 第一個(gè)二叉樹不動(dòng)，從第二棵開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵根結(jié)點(diǎn)的右孩子
3)二叉樹 ——> 樹
是上面樹到二叉樹的逆過程
4)二叉樹 ——> 森林
如果這棵二叉樹有右孩子，那么該二叉樹就能轉(zhuǎn)換為森林是上面森林到二叉樹的逆過程
(2)樹與森林的遍歷
1)樹的遍歷
先根遍歷 (類似先序遍歷)
后跟遍歷 (類似后跟遍歷)
2)森林遍歷
前序遍歷(先訪問第一棵樹，每棵樹內(nèi)用先根遍歷)
后序遍歷(先訪問第一棵樹，每棵樹內(nèi)用后跟遍歷)
注意：森林的前序遍歷和二叉樹的前序遍歷結(jié)果相同
森林的后序遍歷和二叉樹的中序遍歷結(jié)果相同
因此，當(dāng)以二叉鏈表來存儲(chǔ)樹時(shí)，其先根遍歷和后根遍歷算法完全同二叉樹的前序遍歷和后序遍歷
這樣就可以將樹和森林這種復(fù)雜問題進(jìn)行簡單處理
6.二叉樹的應(yīng)用：Huffman樹與Huffman編碼
(1)幾個(gè)概念：
1)路徑長度：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支(其實(shí)就是結(jié)點(diǎn)之間的連線)構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑，而把這條路徑上的的分支(即連線)數(shù)目(之和)稱做路徑長度。
注意："路徑長度" 是針對(duì)任意兩個(gè)結(jié)點(diǎn)間而言的
2)樹的路徑長度：指從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和(對(duì)就是字面意思_)
3)結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到樹根結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)值的乘積
4)樹的帶權(quán)路徑(WPL)：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑之和
WPL = ∑ W(k)*L(K)
其中，W(k)為葉子結(jié)點(diǎn)的權(quán)值，L(k)為葉子結(jié)點(diǎn)的路徑長度
5)Huffman樹：把WPL最小的二叉樹稱為Huffman樹
(2)如何構(gòu)造Huffman樹 ?
根據(jù)Huffman樹的定義知：要想使WPL最小，必須是權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。
基本思想如下：
ⅰ)把所有包含權(quán)值的數(shù)據(jù)元素(w1, w2, ..., wn)看成離散的葉子結(jié)點(diǎn)，并組成"結(jié)點(diǎn)集合": F={w1, w2, ..., wn}
ⅱ)從集合中選取權(quán)值最小的和次小的兩個(gè)葉子結(jié)點(diǎn)作為左右子樹構(gòu)造成一棵新的二叉樹，則該二叉樹的根結(jié)點(diǎn)(記為，R(i)，i表示第i個(gè)合成的根結(jié)點(diǎn) )的權(quán)值為其左右子樹根結(jié)點(diǎn)的權(quán)值之和
ⅲ)從結(jié)點(diǎn)集合中剔除剛選取過的作為左右子樹的那兩個(gè)葉子結(jié)點(diǎn)，并將新構(gòu)建的二叉樹的根結(jié)點(diǎn)(為R(i) )加入到結(jié)點(diǎn)集合中。
ⅳ)重復(fù)(ⅱ)(ⅲ)兩步，當(dāng)集合中只剩下一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)就是所建立的Huffman樹的根結(jié)點(diǎn)，該二叉樹便為Huffman樹
注意：對(duì)于一組給定的葉子結(jié)點(diǎn)所組成的Huffman樹，其樹形可能不相同，但其WPL一定是相等的，且為最小
(3)Huffman編碼
Huffman樹最早是用于優(yōu)化電文編碼的。減小電文編碼長度，節(jié)約存儲(chǔ)或傳輸成本。
如：A B C D E F (字符，即葉子結(jié)點(diǎn))
27 8 15 15 30 5 (字符出現(xiàn)的頻率或權(quán)值)
構(gòu)造Huffman樹
將Huffman樹的左分支代表0,右分支代表1
則，相應(yīng)的Huffman編碼：
A B C D E F
01 1001 101 00 11 1000
○
╱ ╲
╱ ╲
(42) (58)
╱ ╲ ╱ ╲
D(15) A(27) (28) E(30)
╱ ╲
(13) C(15)
╱ ╲
F(5) B(8)
