Java是一種可以撰寫跨平臺應(yīng)用軟件的面向?qū)ο蟮某绦蛟O(shè)計(jì)語言。Java 技術(shù)具有卓越的通用性承粤、高效性暴区、平臺移植性和安全性，廣泛應(yīng)用于PC辛臊、數(shù)據(jù)中心仙粱、游戲控制臺、科學(xué)超級計(jì)算機(jī)彻舰、移動電話和互聯(lián)網(wǎng)伐割，同時(shí)擁有全球最大的開發(fā)者專業(yè)社群。

給你學(xué)習(xí)路線：html-css-js-jq-javase-數(shù)據(jù)庫-jsp-servlet-Struts2-hibernate-mybatis-spring4-springmvc-ssh-ssm

本文撇開一些非逞妥瘢苦澀口猜、難以理解的概念來講講二叉樹，僅入門觀看(或復(fù)習(xí))....

首先透揣，我們來講講什么是樹：

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)济炎，相對于線性的數(shù)據(jù)結(jié)構(gòu)(鏈表、數(shù)組)而言辐真，樹的平均運(yùn)行時(shí)間更短(往往與樹相關(guān)的排序時(shí)間復(fù)雜度都不會高)

在現(xiàn)實(shí)生活中须尚，我們一般的樹長這個(gè)樣子的：

小編推薦一個(gè)學(xué)Java的學(xué)習(xí)裙【 六五零，五五四侍咱，六零七 】耐床，無論你是大牛還是小白，是想轉(zhuǎn)行還是想入行都可以來了解一起進(jìn)步一起學(xué)習(xí)楔脯！裙內(nèi)有開發(fā)工具撩轰，很多干貨和技術(shù)資料分享！

但是在編程的世界中昧廷，我們一般把樹“倒”過來看堪嫂，這樣容易我們分析：

一般的樹是有很多很多個(gè)分支的，分支下又有很多很多個(gè)分支木柬，如果在程序中研究這個(gè)會非常麻煩皆串。因?yàn)楸緛?b>樹就是非線性的，而我們計(jì)算機(jī)的內(nèi)存是線性存儲的眉枕，太過復(fù)雜的話我們無法設(shè)計(jì)出來的恶复。

因此怜森，我們先來研究簡單又經(jīng)常用的--->?二叉樹

1.1樹的一些概念

我就拿上面的圖來進(jìn)行畫來講解了：

二叉樹的意思就是說：每個(gè)節(jié)點(diǎn)不能多于有兩個(gè)兒子，上面的圖就是一顆二叉樹谤牡。

一棵樹至少會有一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))

樹由節(jié)點(diǎn)組成副硅，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是這樣的：

因此，我們定義樹的時(shí)候往往是->定義節(jié)點(diǎn)->節(jié)點(diǎn)連接起來就成了樹拓哟，而節(jié)點(diǎn)的定義就是：一個(gè)數(shù)據(jù)想许、兩個(gè)指針(如果有節(jié)點(diǎn)就指向節(jié)點(diǎn)伶授、沒有節(jié)點(diǎn)就指向null)

1.2靜態(tài)創(chuàng)建二叉樹

上面說了断序，樹是由若干個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)連接起來就成了樹糜烹，而節(jié)點(diǎn)由一個(gè)數(shù)據(jù)违诗、兩個(gè)指針組成

因此，創(chuàng)建樹實(shí)際上就是創(chuàng)建節(jié)點(diǎn)疮蹦，然后連接節(jié)點(diǎn)

首先诸迟，使用Java類定義節(jié)點(diǎn)：

下面我們就拿這個(gè)二叉樹為例來構(gòu)建吧：

為了方便構(gòu)建，我就給了它一個(gè)帶參數(shù)的構(gòu)造方法和set愕乎、get方法了：

那么我們現(xiàn)在就創(chuàng)建了5個(gè)節(jié)點(diǎn)：

它們目前的狀態(tài)是這樣子的：

于是下面我們?nèi)グ阉B起來：

連接完之后，那么我們的樹就創(chuàng)建完成了比肄。

1.3遍歷二叉樹

上面說我們的樹創(chuàng)建完成了搪花，那怎么證明呢吼拥？授账？我們如果可以像數(shù)組一樣遍歷它(看它的數(shù)據(jù))屋确，那就說明它創(chuàng)建完成了～

值得說明的是：二叉樹遍歷有三種方式

先序遍歷

先訪問根節(jié)點(diǎn)，然后訪問左節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)(根->左->右)

中序遍歷

先訪問左節(jié)點(diǎn)悉稠，然后訪問根節(jié)點(diǎn)衰絮，最后訪問右節(jié)點(diǎn)(左->根->右)

后序遍歷

先訪問左節(jié)點(diǎn)煌恢，然后訪問右節(jié)點(diǎn)，最后訪問根節(jié)點(diǎn)(左->右->根)

以上面的二叉樹為例：

如果是先序遍歷：10->9->20->15->35

如果是中序遍歷：9->10->15->20->35

可能需要解釋地方：訪問完10節(jié)點(diǎn)過后，去找的是20節(jié)點(diǎn)授瘦，但20下還有子節(jié)點(diǎn)，因此先訪問的是20的左兒子15節(jié)點(diǎn)竟宋。由于15節(jié)點(diǎn)沒有兒子了提完。所以就返回20節(jié)點(diǎn)，訪問20節(jié)點(diǎn)袜硫。最后訪問35節(jié)點(diǎn)

如果是后序遍歷：9->15->35->20->10

可能需要解釋地方：先訪問9節(jié)點(diǎn)氯葬，隨后應(yīng)該訪問的是20節(jié)點(diǎn)挡篓，但20下還有子節(jié)點(diǎn)婉陷，因此先訪問的是20的左兒子15節(jié)點(diǎn)。由于15節(jié)點(diǎn)沒有兒子了官研。所以就去訪問35節(jié)點(diǎn)秽澳，由于35節(jié)點(diǎn)也沒有兒子了，所以返回20節(jié)點(diǎn)戏羽，最終返回10節(jié)點(diǎn)

一句話總結(jié)：先序(根->左->右)担神，中序(左->根->右)，后序(左->右->根)始花。如果訪問有孩子的節(jié)點(diǎn)妄讯，先處理孩子的，隨后返回

無論先中后遍歷酷宵，每個(gè)節(jié)點(diǎn)的遍歷如果訪問有孩子的節(jié)點(diǎn)亥贸，先處理孩子的(邏輯是一樣的)

因此我們很容易想到遞歸

遞歸的出口就是：當(dāng)沒有子節(jié)點(diǎn)了，就返回

因此浇垦，我們可以寫出這樣的先序遍歷代碼：

結(jié)果跟我們剛才說的是一樣的：

我們再用中序遍歷調(diào)用一遍吧：

結(jié)果跟我們剛才說的是一樣的：

有意思的是：通過先序和中序或者中序和后序我們可以還原出原始的二叉樹炕置，但是通過先序和后續(xù)是無法還原出原始的二叉樹的

也就是說：通過中序和先序或者中序和后序我們就可以確定一顆二叉樹了！

二男韧、動態(tài)創(chuàng)建二叉樹

上面我們是手動創(chuàng)建二叉樹的朴摊，一般地：都是給出一個(gè)數(shù)組給你，讓你將數(shù)組變成一個(gè)二叉樹此虑，此時(shí)就需要我們動態(tài)創(chuàng)建二叉樹了甚纲。

二叉樹中還有一種特殊的二叉樹：二叉查找樹(binary search tree)

定義：當(dāng)前根節(jié)點(diǎn)的左邊全部比根節(jié)點(diǎn)小，當(dāng)前根節(jié)點(diǎn)的右邊全部比根節(jié)點(diǎn)大朦前。

明眼人可以看出介杆，這對我們來找一個(gè)數(shù)是非常方便快捷的

往往我們動態(tài)創(chuàng)建二叉樹都是創(chuàng)建二叉查找樹

小編推薦一個(gè)學(xué)Java的學(xué)習(xí)裙【 六五零讹弯，五五四，六零七 】这溅，無論你是大牛還是小白组民，是想轉(zhuǎn)行還是想入行都可以來了解一起進(jìn)步一起學(xué)習(xí)！裙內(nèi)有開發(fā)工具悲靴，很多干貨和技術(shù)資料分享臭胜！

2.1動態(tài)創(chuàng)建二叉樹體驗(yàn)

假設(shè)我們有一個(gè)數(shù)組：

int[] arrays = {3, 2, 1, 4, 5};

那么創(chuàng)建二叉樹的步驟是這樣的：

首先將3作為根節(jié)點(diǎn)

隨后2進(jìn)來了，我們跟3做比較癞尚，比3小耸三，那么放在3的左邊

隨后1進(jìn)來了，我們跟3做比較浇揩，比3小仪壮，那么放在3的左邊，此時(shí)3的左邊有2了胳徽，因此跟2比积锅，比2小，放在2的左邊

隨后4進(jìn)來了养盗，我們跟3做比較缚陷，比3大，那么放在3的右邊

隨后5進(jìn)來了往核，我們跟3做比較箫爷，比3大，那么放在3的右邊聂儒，此時(shí)3的右邊有4了虎锚，因此跟4比，比4大衩婚，放在4的右邊

那么我們的二叉查找樹就建立成功了窜护，無論任何一顆子樹，左邊都比根要小谅猾，右邊比根要大

2.2代碼實(shí)現(xiàn)

我們的代碼實(shí)現(xiàn)也很簡單柄慰，如果比當(dāng)前根節(jié)點(diǎn)要小，那么放到當(dāng)前根節(jié)點(diǎn)左邊税娜，如果比當(dāng)前根節(jié)點(diǎn)要大坐搔，那么放到當(dāng)前根節(jié)點(diǎn)右邊。

因?yàn)槭莿討B(tài)創(chuàng)建的敬矩，因此我們得用一個(gè)類來表示根節(jié)點(diǎn)

比較與根誰大概行，大的往右邊，小的往左邊：

測試代碼：

三弧岳、查詢二叉查找樹相關(guān)

3.1查詢樹的深度

查詢樹的深度我們可以這樣想：左邊的子樹和右邊的字?jǐn)?shù)比凳忙，誰大就返回誰业踏，那么再接上根節(jié)點(diǎn)+1就可以了

3.1查詢樹的最大值

從上面先序遍歷二叉查找樹的時(shí)候，細(xì)心的同學(xué)可能會發(fā)現(xiàn)：中序遍歷二叉查找樹得到的結(jié)果是排好順序的～

那么涧卵，如果我們的二叉樹不是二叉查找樹勤家，我們要怎么查詢他的最大值呢？

可以這樣：

小編推薦一個(gè)學(xué)Java的學(xué)習(xí)裙【 六五零柳恐，五五四伐脖，六零七 】，無論你是大牛還是小白乐设，是想轉(zhuǎn)行還是想入行都可以來了解一起進(jìn)步一起學(xué)習(xí)讼庇！裙內(nèi)有開發(fā)工具，很多干貨和技術(shù)資料分享近尚！

左邊找最大值->遞歸

右邊找最大值->遞歸

四蠕啄、最后

無論是在遍歷樹、查找深度戈锻、查找最大值都用到了遞歸歼跟，遞歸在非線性的數(shù)據(jù)結(jié)構(gòu)中是用得非常多的...

樹的應(yīng)用也非常廣泛，此篇簡單地說明了樹的數(shù)據(jù)結(jié)構(gòu)舶沛，高級的東西我也沒弄懂嘹承，可能以后用到的時(shí)候會繼續(xù)深入...