如何建立二叉樹

樹

在程式設計世界中，樹其實是一種

非線性

的資料結構，相對於線性的資料結構（連結串列、陣列）而言，

樹的平均執行時間更短(往往與樹相關的排序時間複雜度都不會高)

在現實生活中，我們一般的樹長這個樣子的：

但是在我們實際程式設計的世界中，我們一般把樹“倒”過來看，從根到開始讀起。如下圖所示：

為什麼需要二叉樹這種資料結構

1、陣列儲存方式的分析

優點：透過下標方式訪問元素，速度快。對於有序陣列，還可使用二分查詢提 高檢索速度。

缺點：如果要插入值

(

按一定順序

)

會整體移動，效率較低

畫出操作示意圖：

2、連結串列儲存方式的分析

優點：在一定程度上對陣列的儲存方式有最佳化（比如：插入一個數值節點，只需要將插入節點，連結到連結串列中就行了，刪除效率也不錯）

缺點：在進行檢索時，效率仍然較低，比如（檢索某個值，需要從頭節點開始遍歷）

操作示意圖：

樹儲存方式的分析

能保證提高資料儲存，讀取的效率，比如利用二叉排序樹，即可以保證資料的檢索速度，同時也可以保證資料的插入，刪除，修改的速度。

案例

:

［7， 3， 10， 1， 5， 9， 12］

樹的常用術語

樹的常用術語（結合示意圖理解）：1） 節點2）根節點3）父節點4）子節點5）葉子節點（沒有子節點的節點）6）節 點的權（節點值）7）路徑（從root節點找到該節點的路線）8）層9）子樹10）樹的高度（最大層數）

二叉樹是什麼

1）樹有很多種，每個節點最多隻能有兩個子節點的一種形式稱為二叉樹。

2）二叉樹的子節點分為左節點和右節點

3）示意圖

4）如果該二叉樹的

所有葉子節點都在最後一層

，

並且結點總數=

2^n -1

， n 為層數，則我們稱為滿二叉樹。

5）如果該二叉樹的所有葉子節點都在

最後一層或者倒數第二層

，而且

最後一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續

，我們稱為完全二叉樹。

如何建立二叉樹

靜態建立二叉樹

由上面的知識瞭解到了二叉樹是由多個節點組成的，而節點與節點之間的連結就成了樹。

所以首先建立樹的過程是先建立多個節點。然後將節點與節點之間連線起來。下面是程式碼：

class TreeNode{ private int no；//資料 private TreeNode left； //左節點 private TreeNode right；//右節點 public int getNo（） { return no； } public void setNo（int no） { this。no = no； } public TreeNode getLeft（） { return left； } public void setLeft（TreeNode left） { this。left = left； } public TreeNode getRight（） { return right； } public void setRight（TreeNode right） { this。right = right； }}

下面我們就拿這個二叉樹為例來構建吧：

//根節點 TreeNode treeNode = new TreeNode（10）； //左節點——>9 TreeNode treeNode2 = new TreeNode（9）； //右節點——>20 TreeNode treeNode3 = new TreeNode（20）； //20的左節點——>15 TreeNode treeNode4 = new TreeNode（15）； //20的右節點——>35 TreeNode treeNode5 = new TreeNode（35）； //根節點的左節點 treeNode。setLeft（treeNode2）； //根節點的右節點 treeNode。setRight（treeNode3）； //20節點的左節點 treeNode3。setLeft（treeNode4）； //20節點的右節點 treeNode3。setRight（treeNode5）；

二叉樹遍歷

使用前序，中序和後序對下面的二叉樹進行遍歷。

1） 前序遍歷： 先輸出父節點，再遍歷左子樹和右子樹

2） 中序遍歷： 先遍歷左子樹，再輸出父節點，再遍歷右子樹

3） 後序遍歷： 先遍歷左子樹，再遍歷右子樹，最後輸出父節點

4） 小結：

看輸出父節點的順序，就確定是前序，中序還是後序

以上圖的二叉樹為例：

分析二叉樹的前序，中序，後序的遍歷步驟1。建立一顆二叉樹2。 前序遍歷2。1先輸出當前節點（初始的時候是root節點）2。2如果左子節點不為空，則遞迴繼續前序遍歷2。2如果右子節點不為空，則遞迴繼續前序遍歷 10->9->20->15->353。中序遍歷3。1如果當前節點的左子節點不為空，則遞迴中序遍歷，3。2輸出當前節點3。2如果當前節點的右子節點不為空，則遞迴中序遍歷 9->10->15->20->354。後序遍歷3。1如果當前節點的左子節點不為空，則遞迴後序遍歷，3。2如果當前節點的右子節點不為空，則遞迴後序遍歷3。3輸出當前節點   9->15->35->20->10

下面程式碼演示：

/** * 前序遍歷 */ public void preOrder（）{ //輸出當前節點 System。out。println（this）； //遞歸向左子樹前序遍歷 if（this。left！=null）{ this。left。preOrder（）； } //遞歸向右子樹前序遍歷 if（this。right！=null）{ this。right。preOrder（）； } } /** * 中序遍歷 */ public void indexOrder（）{ //遞歸向左子樹前序遍歷 if（this。left！=null）{ this。left。indexOrder（）； } //輸出當前節點 System。out。println（this）； //遞歸向右子樹前序遍歷 if（this。right！=null）{ this。right。indexOrder（）； } } /** * 後序遍歷 */ public void postOrder（）{ //遞歸向左子樹前序遍歷 if（this。left！=null）{ this。left。postOrder（）； } //遞歸向右子樹前序遍歷 if（this。right！=null）{ this。right。postOrder（）； } //輸出當前節點 System。out。println（this）； }

最後結果

二叉樹-查詢指定節點

要求

1） 請編寫前序查詢，中序查詢和後序查詢的方法。

2） 並分別使用三種查詢方式，查詢 value = 15 的節點

3） 並分析各種查詢方式，分別比較了多少次

4） 思路分析圖解

使用前序，中序，後序的方式來查詢指定的結點

前序查詢思路

1。先判斷當前結點的no是否等於要查詢的

2。如果是相等，則返回當前結點

3。如果不等，

則判斷當前結點的左子節點是否為空

，如果不為空，則遞迴前序查詢

4。如果左遞迴前序查詢，找到結點，則返回，否繼續判斷，當前的結點的右子節點是否為空，如果不空，則繼續向右遞迴前序查詢。

中序查詢思路

1。 判斷當前結點的左子節點是否為空，如果不為空，則遞迴中序查詢

2。如果找到，則返回，如果沒有找到，就和當前結點比較，如果是則返回當前結點，否則繼續進行右遞迴的中序查詢

3。如果右遞迴中序查詢，找到就返回，否則返回null

後序查詢思路

1。判斷當前結點的左子節點是否為空，如果不為空，則遞迴後序查詢

2。如果找到，就返回，如果沒有找到，就判斷當前結點的右子節點是否為空，如果不為空，則右遞迴進行後序查詢，如果找到，就返回

3。就和當前結點進行，比如，如果是則返回，否則返回null

歡迎大家關注我的公眾號：java學習之路，長期分享各種技術文章