二叉樹結構簡介|學習筆記

開發者學堂課程【Java 進階程式設計：二叉樹結構簡介】學習筆記，與課程緊密聯系，讓使用者快速學習知識。

課程位址：

https://developer.aliyun.com/learning/course/20/detail/363

二叉樹結構簡介

内容介紹：

1. 二叉樹相關知識簡介

2. 構造二叉樹的原理

3. 二叉樹的周遊

一、有關二叉樹的介紹

在進行連結清單結構開發的過程之中會發現所有的資料按照收尾相連的狀态進行儲存，那麼當要進行某一個資料查詢的時候（判斷該資料是否存在)，這種情況下它所面對的時間複雜度是“O(n)"。

如果說現在它的資料量小（不超過三十個）的情況下，那麼性能上是不會有太大差别的，而一旦儲存的資料量很大，這個時候時間複雜度就會嚴重損耗程式的運作性能，那麼對于資料的存儲結構就必須發生改變，應該可以盡可能的減少檢索次數為出發點進行設計，對于現在的資料結構而言，最好的性能就是“O（logn),是以現在要想實作它就可以利用二叉樹的結構來完成。

二、構造二叉樹的原理

如果想要實作一顆樹結構的定義，那麼就需要去考慮資料的存儲形式。

在二叉樹的實作之中其基本的實作原理如下:取一個資料為儲存的根節點，小于根節點的資料要放在節點的左子樹，而大于節點的資料要放在該節點的右子樹。

如果要進行資料檢索的話，此時就需要進行每個節點的判斷，但判斷是區分左右的，是以不會整個結構都進行判斷處理，那麼它的時間複雜度就是 O(logn)。

三、二叉樹的周遊

而對于二叉樹而言，在進行資料擷取的時候也有三種形式:

（1） 前序周遊(根-左-右)

（2）中序周遊（左-根-右）

（3） 後序周遊（左-右-根)，