摘要：有網(wǎng)友私信我，期待我的下一篇數(shù)據(jù)結(jié)構(gòu)。前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)里一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)樹，相應(yīng)的會(huì)補(bǔ)充一些算法。除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)又可以分為多個(gè)不相交的子樹。

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。
有網(wǎng)友私信我，期待我的下一篇數(shù)據(jù)結(jié)構(gòu)。非常榮幸文章被認(rèn)可，也非常感謝你們的監(jiān)督。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)里一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)——樹（Tree），相應(yīng)的會(huì)補(bǔ)充一些算法。本篇主要介紹一些必知必會(huì)的，可能是考試中的，也可能是面試中的。

二叉樹及操作

二叉樹的查找算法

B樹、B+樹

Huffman(哈夫曼)樹和Huffman編碼

堆(Heap)和堆排序

紅黑樹

人生苦短，學(xué)會(huì)淡定。。。

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成的一種具有層次關(guān)系的集合，之所以稱之為樹，是因?yàn)樗L(zhǎng)得像一顆倒過(guò)來(lái)的樹。
舉個(gè)例子，每個(gè)人都有家族樹，家族樹一般長(zhǎng)這樣：

家族樹的樣子看起來(lái)像一顆正常的樹，而數(shù)據(jù)結(jié)構(gòu)中的樹則像是一顆倒過(guò)來(lái)的樹：

可以看出，一棵樹有多個(gè)節(jié)點(diǎn)，上圖中帶〇的字母就是一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)可能有0個(gè)或更多子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)至多有一個(gè)父節(jié)點(diǎn)，沒有父節(jié)點(diǎn)的那個(gè)稱之為根節(jié)點(diǎn)。除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)又可以分為多個(gè)不相交的子樹。

1)節(jié)點(diǎn)

樹中每個(gè)元素都叫節(jié)點(diǎn)

2)根節(jié)點(diǎn)或樹根

樹頂端的節(jié)點(diǎn)稱之為根節(jié)點(diǎn)，也叫樹根

3)子樹

除根節(jié)點(diǎn)之外，其他節(jié)點(diǎn)可以分為多個(gè)樹的集合，叫做子樹，在上圖中，K這個(gè)節(jié)點(diǎn)可以稱之為一顆子樹，而H、K、L三個(gè)節(jié)點(diǎn)組合起來(lái)也可以叫做一顆子樹

4)節(jié)點(diǎn)的度

一個(gè)節(jié)點(diǎn)直接含有的子樹的個(gè)數(shù)，稱之為節(jié)點(diǎn)的度。比如上圖中B節(jié)點(diǎn)的度為3，C節(jié)點(diǎn)的度是2，I、J、K、L節(jié)點(diǎn)的度是0

5)葉子節(jié)點(diǎn)、葉節(jié)點(diǎn)、終端節(jié)點(diǎn)

度為0的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)，也叫葉節(jié)點(diǎn)、終端節(jié)點(diǎn)，其實(shí)就是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，或者說(shuō)沒有子樹的節(jié)點(diǎn)

6)雙親節(jié)點(diǎn)、父節(jié)點(diǎn)

父節(jié)點(diǎn)就是一個(gè)節(jié)點(diǎn)上頭的那個(gè)節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)包含若干子節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是這些子節(jié)點(diǎn)的父節(jié)點(diǎn)，也叫雙親節(jié)點(diǎn)

7)兄弟節(jié)點(diǎn)

擁有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)

8)樹的度

一棵樹中最大節(jié)點(diǎn)的度稱之為樹的度，即樹中哪個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)最多，那么這個(gè)節(jié)點(diǎn)的度也就是樹的度

9)節(jié)點(diǎn)的層次

從根這一層開始，根算1層，根的子節(jié)點(diǎn)算2層，一直到最下面一層

10)樹的高度、深度

樹的深度是從根節(jié)點(diǎn)開始、自頂向下逐層累加（根節(jié)點(diǎn)的高度是1）助記：深度從上到下
樹的高度是從葉節(jié)點(diǎn)開始、自底向上逐層累加（葉節(jié)點(diǎn)的高度是1）助記：高度由下向上
雖然樹的高度和深度一樣，但是具體到某個(gè)節(jié)點(diǎn)上，其高度和深度通常是不一樣的。

11)堂兄弟節(jié)點(diǎn)

堂兄弟節(jié)點(diǎn)是同一層，父節(jié)點(diǎn)不同，或者說(shuō)雙親節(jié)點(diǎn)在同一層的節(jié)點(diǎn)稱之為堂兄弟節(jié)點(diǎn)

12)節(jié)點(diǎn)的祖先

從根節(jié)點(diǎn)到某一節(jié)點(diǎn)一路順下來(lái)的除了該節(jié)點(diǎn)的所有節(jié)點(diǎn)都是該節(jié)點(diǎn)的祖先節(jié)點(diǎn)

13)節(jié)點(diǎn)的子孫

以某節(jié)點(diǎn)為根的子樹中，任何一個(gè)節(jié)點(diǎn)都是其子孫，也就是說(shuō)這個(gè)節(jié)點(diǎn)下面與這個(gè)節(jié)點(diǎn)有關(guān)的節(jié)點(diǎn)都是這個(gè)節(jié)點(diǎn)的子孫

14)森林

由m棵不相交的樹組成的集合，叫做森林

樹的種類有很多，我們接觸到的樹有二叉樹、平衡二叉樹、二叉查找樹、B樹、B+樹、哈夫曼樹、B*樹、紅黑樹和trie樹等。

樹，首先首先是由節(jié)點(diǎn)組成，而除根節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)一定只有一個(gè)父節(jié)點(diǎn)，所以可以利用每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)的特性，使用父節(jié)點(diǎn)來(lái)構(gòu)造樹。

public class TreeNode1{
    private int data;
    private int parent;
    
    public int getData(){
        return date;
    }
    public void setData(int data){
        this.data = data;
    }
    
    public int getParent(){
        return parent;
    }
    public void setParent(int parent){
        this.parent = parent;
    }
}

這個(gè)節(jié)點(diǎn)有兩個(gè)屬性，一個(gè)是data，也就是這個(gè)節(jié)點(diǎn)的值(這個(gè)是必須有的)，另一個(gè)是parent，也就是節(jié)點(diǎn)的父節(jié)點(diǎn)。

下一篇更新二叉樹，敬請(qǐng)期待
碼字不易，如對(duì)您有幫助，歡迎點(diǎn)贊收藏打賞^_^