1.6 樹與二叉樹(學吧學吧獨家稿件)
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種資料結構中，所有資料元素之間的關係具有明顯的層次特性。
在樹結構中，每乙個結點只有乙個前件，稱為父結點。沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。每乙個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1)非空二叉樹只有乙個根結點;2)每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
*：根據二叉樹的概念可知，二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上，最多有2k-1(k≥1)個結點。
性質2 深度為m的二叉樹最多有個2m-1個結點。
性質3 在任意一棵二叉樹中，度數為0的結點(即葉子結點)總比度為2的結點多乙個。
性質4 具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
*：根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：
完全二叉樹還具有如下兩個特性：
性質5 具有n個結點的完全二叉樹深度為[log2n]+1。
性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序(每一層從左到右)用自然數1，2，…，n給結點進行編號，則對於編號為k(k=1，2，…，n)的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點的編號為int(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n，則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的儲存結構
在計算機中，二叉樹通常採用鏈式儲存結構。
與線性鍊錶類似，用於儲存二叉樹中各元素的儲存結點也由兩部分組成：資料域和指標域。但在二叉樹中，由於每乙個元素可以有兩個後件(即兩個子結點)，因此，用於儲存二叉樹的儲存結點的指標域有兩個：
乙個用於指向該結點的左子結點的儲存位址，稱為左指標域;另乙個用於指向該結點的右子結點的儲存位址，稱為右指標域。
*：一般二叉樹通常採用鏈式儲存結構，對於滿二叉樹與完全二叉樹來說，可以按層序進行順序儲存[注釋1] 。
5、二叉樹的遍歷(學吧學吧獨家稿件)
二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
(1)前序遍歷(dlr)：若二叉樹為空，則結束返回。否則：
首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
(2)中序遍歷(ldr)：若二叉樹為空，則結束返回。否則：
首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
(3)後序遍歷(lrd)：若二叉樹為空，則結束返回。否則：
首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
注釋1：這樣，不僅節省了儲存空間，又能方便地確定每乙個結點的父結點與左右子結點的位置，但順序儲存結構對於一般的二叉樹不適用。
全國計算機等級考試二級公共基礎知識
第1章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
2019全國計算機等級考試二級公共基礎知識 考試大綱
一 資料結構與演算法 一 基本概念 資料 data 資訊的載體，能夠被計算機識別 儲存和加工處理的物理符號。包括文字型別的資料 如 字母 數字 漢字 和多 型別的資料 如 聲音 動畫 影象 資料元素 data element 是資料的基本單位，有時也稱為元素 結點 頂點 記錄，可以有若干個資料項 字...
全國計算機等級考試二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 1 演算法的基本特徵 可行性 確定性，有窮性 擁有足夠的情報。2 確定性 演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性 3 演算法基本設計方法 列舉法 歸納法 遞推 遞迴 減鬥遞推技術 回溯法。4 通過觀察一些簡單而特殊的情況，最後...