树一：邂逅入门篇
一、樹(shù)的概念
樹(shù)是一種典型的非線性結(jié)構(gòu)，是表達(dá)有層次特性的圖結(jié)構(gòu)的一種方法。
1.1 基本術(shù)語(yǔ)
| 空樹(shù) | 當(dāng)n=0 時(shí)稱為空樹(shù)。 |
| 根結(jié)點(diǎn) | 根結(jié)點(diǎn)是一個(gè)沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)。一棵樹(shù)最多一個(gè)。例如：A |
| 邊 | 結(jié)點(diǎn)之間的連線 |
| 葉子結(jié)點(diǎn) | 沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn)。例如：N、O、P |
| 兄弟結(jié)點(diǎn) | 同一雙親的孩子結(jié)點(diǎn)； 堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn) |
| 祖先結(jié)點(diǎn) | 從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn) |
| 子孫結(jié)點(diǎn) | 以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫 |
| 結(jié)點(diǎn)層 | 根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推； |
| 樹(shù)的深度 | 樹(shù)中最大的結(jié)點(diǎn)層 |
| 樹(shù)的高度 | 跟樹(shù)的深度一個(gè)意思。樹(shù)中所有結(jié)點(diǎn)高度的最大值 |
| 結(jié)點(diǎn)的度 | 結(jié)點(diǎn)子樹(shù)的個(gè)數(shù) |
| 樹(shù)的度 | 樹(shù)中最大的結(jié)點(diǎn)度。 |
| 分枝結(jié)點(diǎn) | 度不為0的結(jié)點(diǎn)； |
| 有序樹(shù) | 子樹(shù)有序的樹(shù)，如：家族樹(shù)； |
| 無(wú)序樹(shù) | 不考慮子樹(shù)的順序 |
注意：有寫書定義書高和層是從0開(kāi)始的。如：根結(jié)點(diǎn)在0層
- 樹(shù)的度
- 如果樹(shù)除了葉子結(jié)點(diǎn)外，其余每一個(gè)結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)，則這種樹(shù)稱為斜樹(shù)； 所有的結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)叫左斜樹(shù)。所有結(jié)點(diǎn)都是只有右子樹(shù)的二叉樹(shù)叫右斜樹(shù)。
1.2 二叉樹(shù)
如果一棵樹(shù)的每個(gè)結(jié)點(diǎn)有0 、1 后者 2個(gè)結(jié)點(diǎn)（最多兩個(gè)孩子結(jié)點(diǎn)），那么這棵樹(shù)稱為二叉樹(shù)。空樹(shù)也是一棵有效的二叉樹(shù)。二叉樹(shù)的子樹(shù)還是二叉樹(shù)。實(shí)際上可以遞歸定義二叉樹(shù)。(因?yàn)檫@個(gè)特性，對(duì)二叉樹(shù)的操作常常使用遞歸算法)
- 滿二叉樹(shù)/滿樹(shù)： 二叉樹(shù)中的每個(gè)結(jié)點(diǎn)恰好有兩個(gè)孩子結(jié)點(diǎn)且所有葉子結(jié)點(diǎn)都在同一層。
- 完全二叉樹(shù)/完全樹(shù)：對(duì)一顆具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層編號(hào)，如果編號(hào)為i(1<=i<=n) 的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中位置完全相同，則這棵二叉樹(shù)稱為完全二叉樹(shù)
倒數(shù)第二層是滿的，且最后一層的葉子結(jié)點(diǎn)從左至右填充
- 平衡二叉樹(shù)： 如果樹(shù)中的每個(gè)結(jié)點(diǎn)的子樹(shù)的高度差不大于1，則樹(shù)稱為高度平衡的或者平衡的。
- 完全平衡樹(shù)： 若二叉樹(shù)中的每個(gè)結(jié)點(diǎn)有兩棵高度相等的子樹(shù)，則該樹(shù)稱為完全平衡樹(shù)。唯一的完全平衡二叉樹(shù)是滿樹(shù)。
- 二叉搜索樹(shù)
二叉查找樹(shù)是一棵二叉樹(shù)、其結(jié)點(diǎn)含有comparable類型的對(duì)象，并遵循以下規(guī)則：
- 平衡二叉查找樹(shù)(AVL 樹(shù))
是平衡樹(shù)和二叉搜索樹(shù)的結(jié)合
在HB(k)中，如果k=1，那么這樣的二叉搜索叫做AVL樹(shù)。即一棵AVL樹(shù)是帶有平衡條件的二叉搜索樹(shù)。 左子樹(shù)和右子樹(shù)的高度最多不能超過(guò)1
- 紅黑色
在紅黑樹(shù)中，每個(gè)結(jié)點(diǎn)關(guān)聯(lián)一個(gè)額外的屬性：紅色或者黑色中的一種顏色。
定義：紅黑樹(shù)是一棵滿足以下性質(zhì)的二叉搜索樹(shù)：
1.3 滿樹(shù)(滿二叉樹(shù))或完全樹(shù)(完全二叉樹(shù))的高度
其中h是樹(shù)的高度，如果滿樹(shù)的結(jié)點(diǎn)樹(shù)為n，則有
即含有n個(gè)結(jié)點(diǎn)的滿樹(shù)的高度是 log2(n+1)。含n個(gè)結(jié)點(diǎn)的完全樹(shù)的高度是對(duì) log2(n+1)向上取整。
含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)或滿二叉樹(shù)的高度是對(duì)log2(n+1)向上取整
1.4 其他、 二叉樹(shù)的應(yīng)用
- 編譯器中的表達(dá)式
- 用于數(shù)據(jù)壓縮算法中哈弗曼編碼樹(shù)
- 二叉搜索樹(shù)(查找樹(shù))BST
- 優(yōu)先隊(duì)列(PQ)
……
1.5 二叉樹(shù)的結(jié)構(gòu)
為了簡(jiǎn)單起見(jiàn)，數(shù)據(jù)設(shè)定為整數(shù)
//java語(yǔ)言描述 public class BinaryTreeNode {private int data;private BinaryTreeNode leftTree;private BinaryTreeNode rightTree;…… }1.6 二叉樹(shù)的操作
- 基本操作
- 插入
- 刪除
- 查找
- 遍歷
- 輔助操作
- 樹(shù)大小
- 樹(shù)高
- 樹(shù)最大層
- 給定兩個(gè)或多個(gè)節(jié)點(diǎn)，找最近公共祖先
……
二 、樹(shù)的遍歷
2.1 二叉樹(shù)的遍歷
為了對(duì)樹(shù)結(jié)構(gòu)進(jìn)行處理，需要一種機(jī)制來(lái)遍歷樹(shù)中的結(jié)點(diǎn)。在遍歷過(guò)程中，每個(gè)結(jié)點(diǎn)只能被處理一次，但可以被訪問(wèn)多次。
- 前序遍歷/先序遍歷：
在訪問(wèn)根的子樹(shù)之前訪問(wèn)根。然后訪問(wèn)根的左子樹(shù)中所有的結(jié)點(diǎn)，再訪問(wèn)根的右子樹(shù)中的所有結(jié)點(diǎn)。
遞歸方式
public static void preOrder(BinaryTreeNode root) {if(null != root) {System.out.print(root.getData() + " ");preOrder(root.getLeftTree());preOrder(root.getRightTree());}}非遞歸方式
為了模擬遞歸：首先處理當(dāng)前結(jié)點(diǎn)，在遍歷左子樹(shù)之前，把當(dāng)前結(jié)點(diǎn)保留到棧中，當(dāng)遍歷完左子樹(shù)后，將該元素出棧，然后找打其右子樹(shù)進(jìn)行遍歷。直到棧為空為止。
public static void preOrderNonRecursive(BinaryTreeNode root) {if(null == root) {return;}Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>(); // FILOwhile (true) {while (null != root) {System.out.print(root.getData() + " ");s.push(root);root = root.getLeftTree();}if(s.isEmpty()) {break;}root = s.pop();root = root.getRightTree();}}- 中序遍歷：
在中序遍歷中，根結(jié)點(diǎn)的訪問(wèn)在兩棵子樹(shù)的遍歷中間完成。
遞歸方式：
public static void inOrder(BinaryTreeNode root) {if(null != root) {inOrder(root.getLeftTree());System.out.print(root.getData() + " ");inOrder(root.getRightTree());} }非遞歸方式：
非遞歸中序遍歷類似前序遍歷。唯一區(qū)別是，首先要移動(dòng)到結(jié)點(diǎn)的左子樹(shù)，完成左子樹(shù)的遍歷后，再將結(jié)點(diǎn)出棧進(jìn)行處理。
public static void inOrderNonRecursive(BinaryTreeNode root) {if(null == root) return;Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();while (true) {while (null != root) {stack.push(root);root = root.getLeftTree();}if(stack.isEmpty()) return;BinaryTreeNode node = stack.pop();System.out.print(node.getData() + " ");root = node.getRightTree();}}- 后序遍歷：
訪問(wèn)二叉樹(shù)的根的子樹(shù)中的結(jié)點(diǎn)之后訪問(wèn)樹(shù)的根
遞歸方式：
public static void postorder(BinaryTreeNode root) {if(null != root) {postorder(root.getLeftTree());postorder(root.getRightTree());System.out.print(root.getData() + " ");}}非遞歸方式：
①：前序、中序遍歷中，當(dāng)元素出棧后就不需要再次訪問(wèn)該結(jié)點(diǎn)了，但是后序遍歷中，每個(gè)結(jié)點(diǎn)需要訪問(wèn)兩次。
②：當(dāng)從棧中出棧一個(gè)元素時(shí)，檢查這個(gè)元素與棧頂元素的右子樹(shù)是否相同。如果相同，則說(shuō)明已經(jīng)完成了左、右子樹(shù)的遍歷。此時(shí)，只需要再將棧頂元素出棧一次病輸出該結(jié)點(diǎn)數(shù)據(jù)即可。
- 層序遍歷：
從根開(kāi)始，每次訪問(wèn)一層中的結(jié)點(diǎn)。在同一層中，從左至右訪問(wèn)。
層序遍歷需要借助隊(duì)列來(lái)完成
public static void levelOrder(BinaryTreeNode root) {if(null == root) return;Queue<BinaryTreeNode> queue = new ArrayDeque<>();queue.add(root);BinaryTreeNode temp = null;while (!queue.isEmpty()) {temp = queue.poll();//處理當(dāng)前結(jié)點(diǎn)System.out.print(temp.getData() + " ");if(null != temp.getLeftTree()) {queue.add(temp.getLeftTree());}if(null != temp.getRightTree()) {queue.add(temp.getRightTree());}}}廣度優(yōu)先遍歷：層序遍歷是廣度優(yōu)先遍歷的示例
深度優(yōu)先遍歷：前序遍歷是深度優(yōu)先遍歷的示例
2.2一般樹(shù)的遍歷
一般樹(shù)的遍歷有層序、前序和后序、對(duì)一般樹(shù)而言，中序遍歷不好定義。
三、樹(shù)的示例
一些使用樹(shù)來(lái)組織數(shù)據(jù)的示例。
3.1 表達(dá)式樹(shù)
可以用二叉樹(shù)來(lái)表示其運(yùn)算符為二元運(yùn)算符的代數(shù)表達(dá)式。孩子的次序要與操作樹(shù)的次序想匹配。這樣的二叉樹(shù)稱為表達(dá)式樹(shù)。
事實(shí)上，不需要括號(hào)，樹(shù)也能得到表示中的運(yùn)算符的次序。代數(shù)表達(dá)式有不同的寫法。正常書寫的表達(dá)式，即每個(gè)二元運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)的中間，稱為中綴表達(dá)式。前綴表達(dá)式將每個(gè)運(yùn)算符都放在其兩個(gè)操作的前面，后綴表達(dá)式將每個(gè)運(yùn)算符都放在其兩個(gè)操作數(shù)的后面。
3.2 二叉查找樹(shù) / 二叉搜索樹(shù)
二叉查找樹(shù)是一棵二叉樹(shù)、其結(jié)點(diǎn)含有comparable類型的對(duì)象，并遵循以下規(guī)則：
- 結(jié)點(diǎn)中的數(shù)據(jù)大于結(jié)點(diǎn)左子樹(shù)中的所有數(shù)據(jù)。
- 結(jié)點(diǎn)中的數(shù)據(jù)小于結(jié)點(diǎn)的右子樹(shù)中的所有數(shù)據(jù)。
- 左子樹(shù)和右子樹(shù)也都必須是二叉查找樹(shù)
例如：字符串二叉查找樹(shù)、Jared大于Jared的左子樹(shù)中的所有名字，但小于Jared的右子樹(shù)中的所有名字。
下面是也是一棵二叉查找樹(shù)
注意： 上面二叉查找樹(shù)的定義，隱含表明樹(shù)中的所有項(xiàng)都是不同的。但允許樹(shù)中有重復(fù)的值
二叉查找樹(shù)的形態(tài)是不唯一的。即對(duì)同樣的一組數(shù)據(jù)，可以組成幾棵不同的二叉查找樹(shù)。例如：
3.3 堆
堆(heap) 是其結(jié)點(diǎn)含有 Comparable對(duì)象的一棵完全二叉樹(shù)，且滿足以下條件：每個(gè)結(jié)點(diǎn)的對(duì)象不小于(或不大于)其后代的對(duì)象。 在最大堆中，結(jié)點(diǎn)中的對(duì)象大于或等于其后代的對(duì)象。 在最小堆中，關(guān)系是小于或等于。
最大/小堆的任何結(jié)點(diǎn)的子樹(shù)仍然是最大/小堆。
可以用堆實(shí)現(xiàn)優(yōu)先隊(duì)列
小結(jié)
本篇是對(duì)樹(shù)的一個(gè)入門，講解了樹(shù)的一些基本概念、并對(duì)二叉樹(shù)的三種遍歷做了全面的介紹，給出了java描述。后面講解了一些其他平衡樹(shù)的知識(shí)，也給出了一些樹(shù)的示例。
參考
- 《數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問(wèn)題解析-Java語(yǔ)言描述》
- 《數(shù)據(jù)結(jié)構(gòu)與抽象Java語(yǔ)言描述第4版》
- 參考 【https://xiaozhuanlan.com/topic/7189032546】
總結(jié)
- 上一篇： win7安装用友U8教程详解
- 下一篇： 简单音乐播放器，上一曲下一曲，暂停