符號表的增刪查操作，隨著元素個數(shù)N的增多，其耗時也是線性增多的，時間復(fù)雜度都是O(n)，為了提高運算效率，我們學(xué)習(xí)樹這種數(shù)據(jù)結(jié)構(gòu)。

目錄

一.樹的基本定義

二.樹的相關(guān)術(shù)語

三.二叉樹的基本定義

四.二叉樹的鏈表實現(xiàn)

1.二叉樹結(jié)點類

結(jié)點類API設(shè)計:?編輯

代碼實現(xiàn)：

2.二叉樹API設(shè)計?編輯

3.二叉樹實現(xiàn)思想

五.二叉樹的基礎(chǔ)遍歷

前序遍歷

中序遍歷

后序遍歷

六.二叉樹的層序遍歷

七.二叉樹的最大深度問題

總結(jié)

一.樹的基本定義

樹是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一顆倒掛的樹，也就是說它是根朝上，而葉朝下的。

?樹具有以下特點：
1.每個結(jié)點有零個或多個子結(jié)點；
2.沒有父結(jié)點的結(jié)點為根節(jié)點；
3.每一個非根結(jié)點只有一個父結(jié)點；
4.每個結(jié)點及其后代結(jié)點整體上可以看做是一棵樹，成為當(dāng)前結(jié)點的父結(jié)點的一個子樹；

二.樹的相關(guān)術(shù)語

結(jié)點的度：
一個結(jié)點含有的子樹的個數(shù)稱為該結(jié)點的度
葉結(jié)點：
度為0的結(jié)點稱為葉結(jié)點，也可以叫做終端結(jié)點；
分支結(jié)點：
度不為0的結(jié)點稱為分支結(jié)點，也可以叫做非終端結(jié)點
結(jié)點的層次：
從根結(jié)點開始，根結(jié)點的層次為1，根的直接后繼層次為2，以此類推
結(jié)點的層序編號：
從樹中的結(jié)點，按照從上層到下層，同層從左到右的次序排成一個線性序列，把他們編成連續(xù)的自然數(shù)。
樹的度：
樹中所有結(jié)點的度的最大值
樹的高度(深度)：
樹中結(jié)點的最大層次
森林：
m（m>=0）個互不相交的樹的集合，將一個非空樹的根結(jié)點刪去，樹就變成了一個森林；給森林增加一個統(tǒng)一的根結(jié)點，森林就變成了一棵樹。

孩子結(jié)點：
一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的孩子結(jié)點
雙親結(jié)點（父節(jié)點）：
一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點
兄弟結(jié)點：
同一雙親結(jié)點的孩子結(jié)點間互稱兄弟結(jié)點

三.二叉樹的基本定義

二叉樹就是度不超過2的樹（每個結(jié)點最多有兩個子結(jié)點）

滿二叉樹：
一個二叉樹，如果每一個層的結(jié)點樹都達(dá)到最大值，則這個二叉樹就是滿二叉樹。

完全二叉樹：
葉節(jié)點只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點都集中在蓋層最左邊的若干位置的二叉樹。

四.二叉樹的鏈表實現(xiàn)

1.二叉樹結(jié)點類

按照面向?qū)ο蟮乃枷耄覀冊O(shè)計一個結(jié)點類來描述結(jié)點這個事物。

代碼實現(xiàn)

public class Node <Key,Vaule>{
    //存儲鍵
    public Key key;
    //存儲值
    public Value vaule;
    //記錄左子結(jié)點
    public Node left;
    //記錄右子結(jié)點
    public Node right;
}

二叉樹存儲既可以使用鏈表也可以使用數(shù)組，使用數(shù)組直接把上面的左子樹和右子樹結(jié)點換成int類型的下標(biāo)值即可。

3.二叉樹API設(shè)計

其他補充api：
private Node min(Node x)? ? ? ? 找出指定樹x中，最小鍵所在的結(jié)點
private Node max(Node x)? ? ? ? 找出指定樹x中，最大鍵所在的結(jié)點

4.二叉樹API實現(xiàn)思想

插入方法put實現(xiàn)思想：
1.如果當(dāng)前樹中沒有任何一個結(jié)點，則直接把新結(jié)點當(dāng)做根結(jié)點使用
2.如果當(dāng)前樹不為空，則從根結(jié)點開始：
2.1 如果新結(jié)點的key小于當(dāng)前結(jié)點的key，則繼續(xù)找當(dāng)前結(jié)點的左子結(jié)點
2.2 如果新結(jié)點的key大于當(dāng)前結(jié)點的key，則繼續(xù)找當(dāng)前結(jié)點的右子結(jié)點
2.3 如果新結(jié)點等于當(dāng)前結(jié)點的key，則樹中已經(jīng)存在這樣的結(jié)點，替換該結(jié)點的value值即可。

查詢方法get實現(xiàn)思想：

從根節(jié)點開始：
1.如果要查詢的key小于當(dāng)前結(jié)點的key，則繼續(xù)找當(dāng)前結(jié)點的左子結(jié)點；
2.如果要查詢的key大于當(dāng)前結(jié)點的key，則繼續(xù)找當(dāng)前結(jié)點的右子結(jié)點；
3.如果要查詢的key等于當(dāng)前結(jié)點的key，則樹中返回當(dāng)前結(jié)點的value。

刪除方法delete實現(xiàn)思想：

1.找到被刪除結(jié)點
2.找到被刪除結(jié)點右子樹中的最小結(jié)點minNode
3.刪除右子樹中的最小結(jié)點
4.讓被刪除結(jié)點的左子樹稱為最小結(jié)點minNode的左子樹，讓被刪除結(jié)點的右子樹稱為最小結(jié)點minNode的右子樹
5.讓被刪除結(jié)點的父節(jié)點指向最小結(jié)點minNode

?

五.二叉樹的基礎(chǔ)遍歷

樹的結(jié)構(gòu)和線性表結(jié)構(gòu)不一樣，沒有辦法從頭開始依次向后遍歷，所以存在按照什么樣的搜索路徑進(jìn)行遍歷的問題。

我們可以把二叉樹的遍歷分為以下三種（簡單說就是按什么時候訪問根節(jié)點進(jìn)而分為前中后）：
1.前序遍歷：先訪問根節(jié)點，然后訪問左子樹，最后訪問右子樹。
2.中序遍歷：先訪問左子樹，中間訪問根節(jié)點，最后訪問右子樹。
3.后序遍歷：先訪問左子樹，再訪問右子數(shù)，最后訪問根節(jié)點。

可以看到其實就是三種操作變換順序罷了。

前序遍歷

實現(xiàn)步驟：
1.把當(dāng)前結(jié)點的key放入到隊列中；
2.找到當(dāng)前結(jié)點的左子樹，如果不為空，遞歸遍歷左子樹；
3.找到當(dāng)前結(jié)點的右子樹，如果不為空，遞歸遍歷右子樹。

相關(guān)題目鏈接：

力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

中序遍歷

實現(xiàn)步驟：
1.找到當(dāng)前結(jié)點的左子樹，如果不為空，遞歸遍歷左子樹；
2.把當(dāng)前結(jié)點的key放入到隊列中；
3.找到當(dāng)前結(jié)點的右子樹，如果不為空，遞歸遍歷右子樹。

相關(guān)題目鏈接：

力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

后序遍歷

實現(xiàn)步驟：
1.找到當(dāng)前結(jié)點的左子樹，如果不為空，遞歸遍歷左子樹；
2.找到當(dāng)前結(jié)點的右子樹，如果不為空，遞歸遍歷右子樹；
3.把當(dāng)前結(jié)點的key放入到隊列中。

相關(guān)題目鏈接：
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

六.二叉樹的層序遍歷

所謂層序遍歷，就是從根節(jié)點（第一層開始），依次向下，獲取每一層所有節(jié)點的值，
有二叉樹如下：

那么層序遍歷的結(jié)果是：EBGADFHC。

實現(xiàn)步驟：
1.創(chuàng)建隊列，存儲每一層的結(jié)點；
2.使用循環(huán)從隊列中彈出一個結(jié)點；
2.1獲取當(dāng)前結(jié)點的key；
2.2如果當(dāng)前結(jié)點的左子結(jié)點不為空，則把左子結(jié)點放入到隊列中；
2.3如果當(dāng)前結(jié)點的右子結(jié)點不為空，則把右子結(jié)點放入到隊列中。

題目鏈接：
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

七.二叉樹的最大深度問題

需求：給定一顆樹，計算樹的最大深度（樹的根節(jié)點到最遠(yuǎn)葉子結(jié)點的最長路徑上的結(jié)點數(shù)）。

實現(xiàn)步驟：
1.如果根結(jié)點為空，則最大深度為0；
2.計算左子樹的最大深度；
3.計算右子樹的最大深度；
4.當(dāng)前樹的最大深度=左子樹的最大深度和右子樹的最大深度中的較大者+1

題目鏈接：
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

總結(jié)

可以看到關(guān)于樹的很多操作都要用到遞歸。文章來源地址http://www.zghlxwxcb.cn/news/detail-650618.html

到了這里，關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)（五）--二叉樹入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！