程序員，你心里需要有點(diǎn)樹

看官，不要生氣，我沒有罵你也沒有鄙視你的意思，今天就是想單純的給大伙分享一下樹的相關(guān)知識(shí)，但是我還是想說作為一名程序員，自己心里有沒有點(diǎn)樹？你會(huì)沒點(diǎn)數(shù)嗎？言歸正傳，樹是我們常用的數(shù)據(jù)結(jié)構(gòu)之一，樹的種類很多有二叉樹、二叉查找樹、平衡二叉樹、紅黑樹、B樹、B+樹等等，我們今天就來聊聊二叉樹相關(guān)的樹。

什么是樹?


首先我們要知道什么是樹？我們平常中的樹是往上長有分支的而卻不會(huì)形成閉環(huán)，數(shù)據(jù)結(jié)構(gòu)中的樹跟我們我們平時(shí)看到的樹類似，確切的說是跟樹根長得類似，我畫了一幅圖，讓大家更好的理解樹。



圖１、圖２都是樹，圖３不是樹。每個(gè)紅色的圓圈我們稱之為元素也叫節(jié)點(diǎn)，用線將兩個(gè)節(jié)點(diǎn)連接起來，這兩個(gè)節(jié)點(diǎn)就形成了父子關(guān)系,同一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)成為兄弟節(jié)點(diǎn)，這跟我們家族關(guān)系一樣，同一個(gè)父親的叫做兄弟姐妹，在家族里面最大的稱為老子，樹里面也是一樣的，只是不叫老子，叫做跟節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的叫做葉子節(jié)點(diǎn)。我們拿圖１來做示例，A為根節(jié)點(diǎn)，B、C為兄弟節(jié)點(diǎn)，E、F為葉子節(jié)點(diǎn)。

一顆樹還會(huì)涉及到三個(gè)概念高度、深度、層，我們先來看看這三個(gè)名詞的定義：

高度：節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑，從０開始計(jì)數(shù)

深度：跟節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊數(shù)，從０開始計(jì)數(shù)

層：節(jié)點(diǎn)距離根節(jié)點(diǎn)的距離，從１開始計(jì)數(shù)

知道了三個(gè)名詞的概念之后，我們用一張圖來更加形象的表示這三個(gè)概念。



以上就是樹的基本概念，樹的種類很多，我們主要來學(xué)學(xué)二叉樹。

二叉樹


二叉樹就像它的名字一樣，每個(gè)元素最多有兩個(gè)節(jié)點(diǎn)，分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)。當(dāng)然并不是每個(gè)元素都需要有兩個(gè)節(jié)點(diǎn)，有的可能只有左節(jié)點(diǎn)，有的可能只有右節(jié)點(diǎn)。就像國家開放二胎一樣，也不是每個(gè)人都需要生兩個(gè)孩子。下面我們來看看一顆典型的二叉樹。



基于樹的存儲(chǔ)模式的不同，為了更好的利用存儲(chǔ)空間，二叉樹又分為完全二叉樹和非完全二叉樹，我們先來看看什么是完全二叉樹、非完全二叉樹？

完全二叉樹的定義：葉子節(jié)點(diǎn)都在最底下兩層，最后一層的葉子節(jié)點(diǎn)都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大

也許單看定義會(huì)看不明白，我們來看幾張圖，你就能夠明白什么是完全二叉樹、非完全二叉樹。

１、完全二叉樹



２、非完全二叉樹



上面我們說了基于樹的存儲(chǔ)模式不同，而分為完全二叉樹和非完全二叉樹，那我們接下來來看看樹的存儲(chǔ)模式。

二叉樹的存儲(chǔ)模式

二叉樹的存儲(chǔ)模式有兩種，一種是基于指針或者引用的二叉鏈?zhǔn)酱鎯?chǔ)法，一種是基于數(shù)組的順序存儲(chǔ)法

二叉鏈?zhǔn)酱鎯?chǔ)法


鏈?zhǔn)酱鎯?chǔ)法相對(duì)比較簡單，理解起來也非常容易，每一個(gè)節(jié)點(diǎn)都有三個(gè)字段，一個(gè)字段存儲(chǔ)著該節(jié)點(diǎn)的值，另外兩個(gè)字段存儲(chǔ)著左右節(jié)點(diǎn)的引用。我們順著跟字節(jié)就可以很輕松的把整棵樹串起來，鏈?zhǔn)酱鎯?chǔ)法的結(jié)構(gòu)大概長成這樣。



順序存儲(chǔ)法

順序存儲(chǔ)法是基于數(shù)組實(shí)現(xiàn)的，數(shù)組是一段有序的內(nèi)存空間，如果我們把跟節(jié)點(diǎn)的坐標(biāo)定位i=1，左節(jié)點(diǎn)就是 2 * i = 2，右節(jié)點(diǎn) 2 * i+ 1 =
3，以此類推，每個(gè)節(jié)點(diǎn)都這么算，然后就將樹轉(zhuǎn)化成數(shù)組了，反過來，按照這種規(guī)則我們也能將數(shù)組轉(zhuǎn)化成一棵樹?？吹竭@里我想你一定看出了一些弊端，
如果這是一顆不平衡的二叉樹是不是會(huì)造成大量的空間浪費(fèi)呢？沒錯(cuò)，這就是為什么需要分完全二叉樹和非完全二叉樹。分別來看看這兩種樹基于數(shù)組的存儲(chǔ)模式。
完全二叉樹順序存儲(chǔ)法

非完全二叉樹順序存儲(chǔ)法


從圖中將樹轉(zhuǎn)化成數(shù)組之后可以看出，完全二叉樹用數(shù)組來存儲(chǔ)只浪費(fèi)了一個(gè)下標(biāo)為0的存儲(chǔ)空間，二非完全二叉樹則浪費(fèi)了大量的空間。
如果樹為完全二叉樹，用數(shù)組存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)節(jié)約空間，因?yàn)閿?shù)組存儲(chǔ)不需要存儲(chǔ)左右節(jié)點(diǎn)的信息

上面我們了解了二叉樹的定義、類型、存儲(chǔ)方式，接下來我們一起了解一下二叉樹的遍歷，二叉樹的遍歷也是面試中經(jīng)常遇到的問題。

二叉樹遍歷


要了解二叉樹的遍歷，我們首先需要實(shí)例化出一顆二叉樹，我們采用鏈?zhǔn)酱鎯?chǔ)的方式來定義樹，實(shí)例化樹需要樹的節(jié)點(diǎn)信息，用來存放該節(jié)點(diǎn)的信息，因?yàn)槲覀儾庞玫氖擎準(zhǔn)酱鎯?chǔ)，所以我們的節(jié)點(diǎn)信息如下。
/** * 定義一棵樹 */ public class TreeNode { // 存儲(chǔ)值 public int data; // 存儲(chǔ)左節(jié)點(diǎn) public
TreeNode left; // 存儲(chǔ)右節(jié)點(diǎn) public TreeNode right; public TreeNode(int data) {
this.data = data; } }
定義完節(jié)點(diǎn)信息之后，我們就可以初始化一顆樹啦，下面是初始化樹的過程:
public static TreeNode buildTree() { // 創(chuàng)建測試用的二叉樹 TreeNode t1 = new
TreeNode(1); TreeNode t2 = new TreeNode(2); TreeNode t3 = new TreeNode(3);
TreeNode t4 = new TreeNode(4); TreeNode t5 = new TreeNode(5); TreeNode t6 = new
TreeNode(6); TreeNode t7 = new TreeNode(7); TreeNode t8 = new TreeNode(8);
t1.left = t2; t1.right = t3; t2.left = t4; t4.right = t7; t3.left = t5;
t3.right = t6; t6.left = t8; return t1; }
經(jīng)過上面步驟之后，我們的樹就長成下圖所示的樣子，數(shù)字代表該節(jié)點(diǎn)的值。



有了樹之后，我們就可以對(duì)樹進(jìn)行遍歷啦，二叉樹的遍歷有三種方式，前序遍歷、中序遍歷、后續(xù)遍歷三種遍歷方式，三種遍歷方式與節(jié)點(diǎn)輸出的順序有關(guān)系。下面我們分別來看看這三種遍歷方式。

前序遍歷

前序遍歷：對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印這個(gè)節(jié)點(diǎn)，然后再打印它的左子樹，最后打印它的右子樹。

為了方便大家的理解，我基于上面我們定義的二叉樹，對(duì)三種遍歷方式的執(zhí)行流程都制作了動(dòng)態(tài)圖，希望對(duì)你的閱讀有所幫助，我們先來看看前序遍歷的執(zhí)行流程動(dòng)態(tài)圖。


理解了前序遍歷的概念和看完前序遍歷執(zhí)行流程動(dòng)態(tài)圖之后，你心里一定很想知道，在代碼中如何怎么實(shí)現(xiàn)樹的前序遍歷？二叉樹的遍歷非常簡單，一般都是采用遞歸的方式進(jìn)行遍歷，我們來看看前序遍歷的代碼：
// 先序遍歷，遞歸實(shí)現(xiàn) 先打印本身，再打印左節(jié)點(diǎn)，在打印右節(jié)點(diǎn) public static void preOrder(TreeNode root) {
if (root == null) { return; } // 輸出本身 System.out.print(root.data + " "); //
遍歷左節(jié)點(diǎn) preOrder(root.left); // 遍歷右節(jié)點(diǎn) preOrder(root.right); }
中序遍歷

中序遍歷：對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后再打印它本身，最后打印它的右子樹。

跟前序遍歷一樣，我們來看看中序遍歷的執(zhí)行流程動(dòng)態(tài)圖。

中序遍歷的代碼：
// 中序遍歷 先打印左節(jié)點(diǎn)，再輸出本身，最后輸出右節(jié)點(diǎn) public static void inOrder(TreeNode root) { if
(root == null) { return; } inOrder(root.left); System.out.print(root.data + "
"); inOrder(root.right); }
后序遍歷

后序遍歷：對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后再打印它的右子樹，最后打印這個(gè)節(jié)點(diǎn)本身。

跟前兩種遍歷一樣，理解概念之后，我們還是先來看張圖。

后序遍歷的實(shí)現(xiàn)代碼：
// 后序遍歷 先打印左節(jié)點(diǎn)，再輸出右節(jié)點(diǎn)，最后才輸出本身 public static void postOrder(TreeNode root) { if
(root == null) { return; } postOrder(root.left); postOrder(root.right);
System.out.print(root.data + " "); }

二叉樹的遍歷還是非常簡單的，雖然有三種遍歷方式，但都是一樣的，只是輸出的順序不一樣而已，經(jīng)過了上面這么多的學(xué)習(xí)，我相信你一定對(duì)二叉樹有不少的認(rèn)識(shí)，接下來我們來了解一種常用而且比較特殊的二叉樹：
二叉查找樹

二叉查找樹


二叉查找樹又叫二叉搜索樹，從名字中我們就能夠知道，這種樹在查找方面一定有過人的優(yōu)勢，事實(shí)確實(shí)如此，二叉查找樹確實(shí)是為查找而生的樹，但是它不僅僅支持快速查找數(shù)據(jù)，還支持快速插入、刪除一個(gè)數(shù)據(jù)。那它是怎么做到這些的呢？我們先從二叉查找樹的概念開始了解。

二叉查找樹：在樹中的任意一個(gè)節(jié)點(diǎn)，其左子樹中的每個(gè)節(jié)點(diǎn)的值，都要小于這個(gè)節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都大于這個(gè)節(jié)點(diǎn)的值。

難以理解？記不?。繘]關(guān)系的，下面我定義了一顆二叉查找樹，我們對(duì)著樹，來慢慢理解。


根據(jù)二叉查找樹的定義，每棵樹的左節(jié)點(diǎn)的值要小于這父節(jié)點(diǎn)，右節(jié)點(diǎn)的值要大于父節(jié)點(diǎn)。62節(jié)點(diǎn)的 所有左節(jié)點(diǎn)的值都要小于 62 ，所有右節(jié)點(diǎn) 的值都要大于 62
。對(duì)于這顆樹上的每一個(gè)節(jié)點(diǎn)都要滿足這個(gè)條件，我們拿我們樹上的另一個(gè)節(jié)點(diǎn) 35 來說，它的右子樹上的節(jié)點(diǎn)值最大不能超過 47 ，因?yàn)?35 是 47
的左子樹，根據(jù)二叉搜索樹的規(guī)則，左子樹的值要小于節(jié)點(diǎn)值。

二叉查找樹既然名字中帶有查找兩字，那我們就從二叉查找樹的查找開始學(xué)習(xí)二叉查找樹吧。

二叉查找樹的查找操作


由于二叉查找樹的特性，我們需要查找一個(gè)數(shù)據(jù)，先跟跟節(jié)點(diǎn)比較，如果值等于跟節(jié)點(diǎn)，則返回根節(jié)點(diǎn)，如果小于根節(jié)點(diǎn)，則必然在左子樹這邊，只要遞歸查找左子樹就行，如果大于，這在右子樹這邊，遞歸右子樹即可。這樣就能夠?qū)崿F(xiàn)快速查找，因?yàn)槊看尾檎叶紲p少了一半的數(shù)據(jù)，跟二分查找有點(diǎn)相似，快速插入、刪除都是居于這個(gè)特性實(shí)現(xiàn)的。

下面我們用一幅動(dòng)態(tài)圖來加強(qiáng)對(duì)二叉查找樹查找流程的理解，我們需要在上面的這顆二叉查找樹中找出值等于 37 的節(jié)點(diǎn)，我們一起來看看流程圖是怎么實(shí)現(xiàn)的。


* 1、先用 37 跟 62 比較，37 < 62 ，在左子樹中繼續(xù)查找
* ２、左子樹的節(jié)點(diǎn)值為 58，37 < 58 ，繼續(xù)在左子樹中查找
* ３、左子樹的節(jié)點(diǎn)值為 47，37 < 47，繼續(xù)在左子樹中查找
* ４、左子樹的節(jié)點(diǎn)值為 35，37 > 35，在右子樹中查找
* ５、右子樹中的節(jié)點(diǎn)值為 37，37 = 37 ，返回該節(jié)點(diǎn)
講完了查找的概念之后，我們一起來看看二叉查找樹的查找操作的代碼實(shí)現(xiàn)
/** * 根據(jù)值查找樹 * @param data　值 * @return */ public TreeNode find(int data) {
TreeNode p = tree; while (p != null) { if (data < p.data) p = p.left; else if
(data > p.data) p = p.right; else return p; } return null; }
二叉查找樹的插入操作


插入跟查找差不多，也是從根節(jié)點(diǎn)開始找，如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大，并且節(jié)點(diǎn)的右子樹為空，就將新數(shù)據(jù)直接插到右子節(jié)點(diǎn)的位置；如果不為空，就再遞歸遍歷右子樹，查找插入位置。同理，如果要插入的數(shù)據(jù)比節(jié)點(diǎn)數(shù)值小，并且節(jié)點(diǎn)的左子樹為空，就將新數(shù)據(jù)插入到左子節(jié)點(diǎn)的位置；如果不為空，就再遞歸遍歷左子樹，查找插入位置。

假設(shè)我們要插入 63 ，我們用一張動(dòng)態(tài)圖來看看插入的流程。


* 1、63 > 62 ，在樹的右子樹繼續(xù)查找.
* 2、63 < 88 ，在樹的左子樹繼續(xù)查找
* 3、63 < 73 ,因?yàn)?73 是葉子節(jié)點(diǎn)，所以 63 就成為了 73 的左子樹。
我們來看看二叉查找樹的插入操作實(shí)現(xiàn)代碼
/** * 插入樹 * @param data */ public void insert(int data) { if (tree == null) {
tree = new TreeNode(data); return; } TreeNode p = tree; while (p != null) { //
如果值大于節(jié)點(diǎn)的值，則新樹為節(jié)點(diǎn)的右子樹 if (data > p.data) { if (p.right == null) { p.right = new
TreeNode(data); return; } p = p.right; } else { // data < p.data if (p.left ==
null) { p.left = new TreeNode(data); return; } p = p.left; } } }
二叉查找樹的刪除操作

刪除的邏輯要比查找和插入復(fù)雜一些，刪除分一下三種情況：

第一種情況：如果要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們只需要直接將父節(jié)點(diǎn)中，指向要?jiǎng)h除節(jié)點(diǎn)的指針置為 null。比如圖中的刪除節(jié)點(diǎn) 51。

第二種情況
：如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（只有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中，指向要?jiǎng)h除節(jié)點(diǎn)的指針，讓它指向要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)就可以了。比如圖中的刪除節(jié)點(diǎn)
35。

第三種情況
：如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，這就比較復(fù)雜了。我們需要找到這個(gè)節(jié)點(diǎn)的右子樹中的最小節(jié)點(diǎn)，把它替換到要?jiǎng)h除的節(jié)點(diǎn)上。然后再刪除掉這個(gè)最小節(jié)點(diǎn)，因?yàn)樽钚」?jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)（如果有左子結(jié)點(diǎn)，那就不是最小節(jié)點(diǎn)了），所以，我們可以應(yīng)用上面兩條規(guī)則來刪除這個(gè)最小節(jié)點(diǎn)。比如圖中的刪除節(jié)點(diǎn)
88

前面兩種情況稍微簡單一些，第三種情況，我制作了一張動(dòng)態(tài)圖，希望能對(duì)你有所幫助。


我們來看看二叉查找樹的刪除操作實(shí)現(xiàn)代碼
public void delete(int data) { TreeNode p = tree; // p指向要?jiǎng)h除的節(jié)點(diǎn)，初始化指向根節(jié)點(diǎn)
TreeNode pp = null; // pp記錄的是p的父節(jié)點(diǎn) while (p != null && p.data != data) { pp =
p; if (data > p.data) p = p.right; else p = p.left; } if (p == null) return; //
沒有找到 // 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn) if (p.left != null && p.right != null) { // 查找右子樹中最小節(jié)點(diǎn)
TreeNode minP = p.right; TreeNode minPP = p; // minPP表示minP的父節(jié)點(diǎn) while
(minP.left != null) { minPP = minP; minP = minP.left; } p.data = minP.data; //
將minP的數(shù)據(jù)替換到p中 p = minP; // 下面就變成了刪除minP了 pp = minPP; } // 刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者僅有一個(gè)子節(jié)點(diǎn)
TreeNode child; // p的子節(jié)點(diǎn) if (p.left != null) child = p.left; else if (p.right
!= null) child = p.right; else child = null; if (pp == null) tree = child; //
刪除的是根節(jié)點(diǎn) else if (pp.left == p) pp.left = child; else pp.right = child; }

我們上面了解了一些二叉查找樹的相關(guān)知識(shí)，由于二叉查找樹在極端情況下會(huì)退化成鏈表，例如每個(gè)節(jié)點(diǎn)都只有一個(gè)左節(jié)點(diǎn)，這是時(shí)間復(fù)雜度就變成了O(n)，為了避免這種情況，又出現(xiàn)了一種新的樹叫
平衡二叉查找樹，由于本文篇幅有點(diǎn)長了，相信看到這里的各位小伙伴已經(jīng)有點(diǎn)疲憊了，關(guān)于平衡二叉查找樹的相關(guān)知識(shí)我就不在這里介紹了。

最后

打個(gè)小廣告，金九銀十跳槽季，平頭哥給大家整理了一份較全面的 Java 學(xué)習(xí)資料，歡迎掃碼關(guān)注微信公眾號(hào)：「平頭哥的技術(shù)博文」領(lǐng)取，祝各位升職加薪。

• ? 上一篇：Docker系列之AspNetCore Runtime VS .NetCore Runtime VS .NET Core SDK（四）
• ? 下一篇：第三代驗(yàn)證碼研究