樹Tree的基本概念
- 節(jié)點(diǎn)、根節(jié)點(diǎn)炼鞠、父節(jié)點(diǎn)缘滥、子節(jié)點(diǎn)轰胁、兄弟節(jié)點(diǎn)
- 一棵樹可以沒有任何節(jié)點(diǎn)谒主，稱為
空樹 - 一棵樹可以只有一個(gè)節(jié)點(diǎn)，也就是只有根節(jié)點(diǎn)
- 子樹赃阀、左子樹霎肯、右子樹
節(jié)點(diǎn)的
度（degree）：子樹的個(gè)數(shù)
??：1的度是5個(gè)：2擎颖、3、4观游、5搂捧、6
??：2的度是2個(gè)：21、22
??：61的度是0個(gè)樹的
度（degree）：所有節(jié)點(diǎn)度中的最大值
??：圖中最大的是節(jié)點(diǎn)1懂缕，有5個(gè)度葉子的節(jié)點(diǎn)（leaf）：度為0的節(jié)點(diǎn)
??：圖中21允跑、221、222搪柑、223聋丝、31、5工碾、51弱睦、52、61都是葉子節(jié)點(diǎn)非葉子的節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)
樹的
層數(shù)（level）：根節(jié)點(diǎn)在第1層渊额，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第2層况木，以此類推（有些教程從第0層計(jì)算）節(jié)點(diǎn)的
深度（depth）：從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的唯一路勁上的節(jié)點(diǎn)總數(shù)
??：節(jié)點(diǎn)2的深度：從根節(jié)點(diǎn)1到2經(jīng)過了2個(gè)節(jié)點(diǎn)，深度為2
??：節(jié)點(diǎn)31的深度：從根節(jié)點(diǎn)1到31經(jīng)過了3個(gè)節(jié)點(diǎn)旬迹，深度為3節(jié)點(diǎn)的
高度（height）：從當(dāng)前節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路勁上的節(jié)點(diǎn)總數(shù)
??：節(jié)點(diǎn)2的高度：圖中看出從節(jié)點(diǎn)2到最遠(yuǎn)的葉子節(jié)點(diǎn)為221火惊、222、223中的一個(gè)奔垦，取其中一個(gè)計(jì)算矗晃，經(jīng)歷了2-22-221總共3個(gè)節(jié)點(diǎn)，所有高度為3樹的
深度：所有節(jié)點(diǎn)深度中的最大值樹的
高度：所有節(jié)點(diǎn)高度中的最大值樹的
深度等于 樹的高度
有序樹宴倍、無序樹张症、森林
- 有序樹：樹中的任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系
- 有序樹：樹中的任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系（也稱為“自由樹”）
- 森林：由
m (m >= 0)棵互不相交的樹組成的集合
二叉樹Binary Tree
二叉樹的特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)的度最大值為
2（最多擁有2棵子樹） - 左子樹跟右子樹是有順序的
- 即使某個(gè)節(jié)點(diǎn)只有一棵子樹，也要區(qū)分左右子樹
- 二叉樹是有序樹
二叉樹的性質(zhì)：
- 非空二叉樹的第
i層鸵贬，最多有 2i-1 個(gè)節(jié)點(diǎn)（i >= 1） - 高度為
h的二叉樹上最多有 2h-1 個(gè)節(jié)點(diǎn)（h>= 1） - 對(duì)于任何一棵非空二叉樹俗他，如果葉子節(jié)點(diǎn)個(gè)數(shù)為
n0，度為2的節(jié)點(diǎn)個(gè)數(shù)為n2阔逼，則有：n0 = n2 + 1
假設(shè)度為1的節(jié)點(diǎn)個(gè)數(shù)為n1兆衅，那么二叉樹的節(jié)點(diǎn)總數(shù)n = n0 + n1 + n2
二叉樹的變數(shù)T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
真二叉樹Proper Binary Tree
- 所有節(jié)點(diǎn)的
度要么是0，要么是2
滿二叉樹Full Binary Tree
- 所有節(jié)點(diǎn)的
度要么是0嗜浮，要么是2羡亩，且所有的葉子節(jié)點(diǎn)都在最后一層 - 在同樣高度的二叉樹中，滿二叉樹的葉子節(jié)點(diǎn)數(shù)量最多危融，總節(jié)點(diǎn)數(shù)量最多
- 滿二叉樹一定是真二叉樹畏铆，真二叉樹不一定是滿二叉樹
- 假設(shè)滿二叉樹的高度為
h（h>= 1），那么：
??：第i層的節(jié)點(diǎn)數(shù)量：2i-1
??：葉子節(jié)點(diǎn)數(shù)量：2h-1
??：總節(jié)點(diǎn)的數(shù)量n：n = 2h-1 = 20 + 21 + 22 + ... 2h-1
完全二叉樹Complete Binary Tree
- 葉子節(jié)點(diǎn)只會(huì)出現(xiàn)在最后
2層吉殃，且最后1層的葉子節(jié)點(diǎn)都靠左對(duì)齊 - 完全二叉樹從
根節(jié)點(diǎn)至倒數(shù)第2層是一棵滿二叉樹 - 滿二叉樹一定是完全二叉樹辞居，完全二叉樹不一定是滿二叉樹
- 度為
1的節(jié)點(diǎn)只有左子樹 - 度為
1的節(jié)點(diǎn)要么是1個(gè)楷怒，要么是0個(gè) - 同樣節(jié)點(diǎn)數(shù)量的二叉樹，完全二叉樹的高度最小
- 假設(shè)完全二叉樹的高度為
h（h>= 1）瓦灶，那么：
??：至少有2h-1個(gè)節(jié)點(diǎn) 20 + 21 + 22 + ... 2h-2 + 1
??：最多有2h-1個(gè)節(jié)點(diǎn) 20 + 21 + 22 + ... 2h-1鸠删，滿二叉樹
??：總節(jié)點(diǎn)數(shù)量：2h-1<=n<=2h，取對(duì)數(shù)：h - 1 <=< h
二叉搜索樹Binary Search Tree
1贼陶、二叉搜索樹是二叉樹的一種刃泡，是應(yīng)用非常廣泛的一種二叉樹，簡(jiǎn)稱BST
- 又稱為：二叉查找樹碉怔、二叉排序樹
- 任意一個(gè)節(jié)點(diǎn)的值都
大于其左子樹所有節(jié)點(diǎn)的值 - 任意一個(gè)節(jié)點(diǎn)的值都
小于其右子樹所有節(jié)點(diǎn)的值 - 它的左右子樹也是一顆二叉搜索樹
2捅僵、二叉搜索樹可以大大提高搜索數(shù)據(jù)的效率
3、二叉搜索樹存儲(chǔ)的元素必須具備可比較性
- 比如
int眨层、double等 - 如果自定義類型庙楚，需要制定比較方式
- 不允許為
null
二叉樹的遍歷
- 遍歷是數(shù)據(jù)結(jié)構(gòu)中常見操作：
1??：把所有元素都訪問一遍 - 線性數(shù)據(jù)結(jié)構(gòu)的遍歷比較簡(jiǎn)單：
1??：正序遍歷
2??：逆序遍歷 - 根據(jù)節(jié)點(diǎn)訪問順序的不同，二叉樹的常見遍歷方式有4種：
1??：前序遍歷
2??：中序遍歷
3??：后序遍歷
4??：層序遍歷
二叉樹的遍歷 —— 前序遍歷
- 訪問順序：
??：根節(jié)點(diǎn)— 前序遍歷左子樹— 前序遍歷右子樹
??：7——4趴樱、2馒闷、1、3叁征、5——9纳账、8、11捺疼、10疏虫、12
可以利用遞歸來實(shí)
public void preporderTraversal() {
preporderTraversal(rootNode);
}
private void preporderTraversal(Node<E> node) {
if (node == null) { return; }
System.out.println(node.element);
preporderTraversal(node.leftNode);
preporderTraversal(node.rightNode);
}
二叉樹的遍歷 —— 中序遍歷
- 訪問順序：
??：中序遍歷左子樹—根節(jié)點(diǎn)— 中序遍歷右子樹
??：1、2啤呼、3卧秘、4、5——7——8官扣、9翅敌、10、11惕蹄、12
- 如果訪問順序是這樣的：
??：中序遍歷右子樹—根節(jié)點(diǎn)— 中序遍歷左子樹
??：12蚯涮、11、10卖陵、9遭顶、8——7——5、4泪蔫、3棒旗、2、1 -
二叉搜索樹的中序遍歷結(jié)果是升序或者降序的
public void inorderTraversal() {
inorderTraversal(rootNode);
}
private void inorderTraversal(Node<E> node) {
if (node == null) { return; }
inorderTraversal(node.leftNode);
System.out.println(node.element);
inorderTraversal(node.rightNode);
}
二叉樹的遍歷 —— 后序遍歷
- 訪問順序：
??：后序遍歷左子樹— 后序遍歷右子樹—根節(jié)點(diǎn)
??：1鸥滨、3嗦哆、2、5婿滓、4——8老速、10、12凸主、11橘券、9——7
public void postorderTraversal() {
postorderTraversal(rootNode);
}
private void postorderTraversal(Node<E> node) {
if (node == null) { return; }
postorderTraversal(node.leftNode);
postorderTraversal(node.rightNode);
System.out.println(node.element);
}
二叉樹的遍歷 —— 層序遍歷
- 訪問順序：
??：從上到下，從左到右依次訪問每一個(gè)節(jié)點(diǎn)
??：7——4卿吐、9——2旁舰、5、8嗡官、1——1箭窜、3、10衍腥、12
- 實(shí)現(xiàn)思路：使用隊(duì)列
1??：將根節(jié)點(diǎn)入隊(duì)
2??：循環(huán)執(zhí)行下面操作磺樱，直到隊(duì)列為空：
??：將隊(duì)頭節(jié)點(diǎn)A出隊(duì)，進(jìn)行訪問
??：將A的左子節(jié)點(diǎn)入隊(duì)
??：將A的右子節(jié)點(diǎn)入隊(duì)
public void levelOrderTraversal() {
if (rootNode == null) { return; }
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(rootNode);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
//是否有左右子節(jié)點(diǎn)
if (node.leftNode != null) {
queue.offer(node.leftNode);
}
if (node.rightNode != null) {
queue.offer(node.rightNode);
}
}
}
