1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種資料結構中，所有資料元素之間的關係具有明顯的層次特性。
在樹結構中，每乙個結點只有乙個前件，稱為父結點。沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。每乙個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
（1）什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有乙個根結點；2）每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。
（2）二叉樹的基本性質
性質1 在二叉樹的第k層上，最多有2k-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、二叉樹的儲存結構
在計算機中，二叉樹通常採用鏈式儲存結構。
與線性鍊錶類似，用於儲存二叉樹中各元素的儲存結點也由兩部分組成：資料域和指標域。但在二叉樹中，由於每乙個元素可以有兩個後件（即兩個子結點），因此，用於儲存二叉樹的儲存結點的指標域有兩個：
乙個用於指向該結點的左子結點的儲存位址，稱為左指標域；另乙個用於指向該結點的右子結點的儲存位址，稱為右指標域。
*：一般二叉樹通常採用鏈式儲存結構，對於滿二叉樹與完全二叉樹來說，可以按層序進行順序儲存。
5、二叉樹的遍歷
二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
（1）前序遍歷（dlr）：若二叉樹為空，則結束返回。否則：
首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷（ldr）：若二叉樹為空，則結束返回。否則：
首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷（lrd）：若二叉樹為空，則結束返回。否則：
首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
這樣，不僅節省了儲存空間，又能方便地確定每乙個結點的父結點與左右子結點的位置，但順序儲存結構對於一般的二叉樹不適用。
二叉樹的遍歷
飛機票訂票系統 二 一四年六月 二叉數的遍歷 1 問題陳述 二叉樹的中序 前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。限1 人完成 二叉樹的前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。先序遍歷二叉樹演算法 若二叉樹為...
二叉樹的操作報告
資料結構 課程設計報告 題目 二叉樹遍歷演算法整合 系別 電腦科學系 班級 計應班 學號姓名 完成日期 2012 年 6 月 29日 指導老師 目錄一 課程設計目的 1 二 課程設計內容 1 三 演算法的基本思想 1 一 棧資料型別定義 1 二 二叉樹資料型別定義 1 三 主要模組設計 2 四 流程...
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...