資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學資料結構中的二叉樹ADT
基本概念
二叉樹定義為：樹中任何節點最多隻有兩個子節點。任何節點的最高度為二。這意味著二叉樹的度為零、一或二。
在上圖中，二叉樹由根節點和兩個子樹 TreeLeft 和 TreeRight 組成。二叉樹左側的所有節點都稱為左子樹，二叉樹右側的所有節點都稱為右子樹。
實現
二叉樹最多有兩個子節點；我們可以直接用指標指向它們。樹節點的宣告與雙向連結串列的結構宣告相同，即一個節點是一個結構體，包含關鍵資訊加上指向其他節點的兩個指標（左和右）。
二叉樹節點宣告
typedef struct tree_node *tree_ptr;
struct tree_node
{
element_type element1;
tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE;二叉樹的型別
嚴格二叉樹
嚴格二叉樹定義為：所有節點都只有零個或兩個子節點的二叉樹。它不包含任何只有一個子節點的節點。
斜樹
斜樹定義為：除葉子節點外，每個節點只有一個子節點的二叉樹。斜樹有兩種型別：左斜二叉樹和右斜二叉樹。
左斜二叉樹
左斜樹的節點只與左子節點相關聯。它是一個只包含左子樹的二叉樹。
右斜二叉樹
右斜樹的節點只與右子節點相關聯。它是一個只包含右子樹的二叉樹。
滿二叉樹或正則二叉樹
如果所有葉子節點都在同一層，並且每個非葉子節點都恰好有兩個子節點，並且它應該包含所有層中儘可能多的節點，則二叉樹定義為滿二叉樹。高度為 h 的滿二叉樹最多有 2h+1 – 1 個節點。
完全二叉樹
每個非葉子節點都恰好有兩個子節點，但並非所有葉子節點都必須位於同一層。完全二叉樹定義為：除最後一層外，所有層都具有最大數量的節點的二叉樹。最後一層的元素應該從左到右填充。
幾乎完全二叉樹
幾乎完全二叉樹定義為：每個具有右子節點的節點也具有左子節點的樹。具有左子節點的節點不需要具有右子節點。
一般樹和二叉樹的區別
一般樹
- 一般樹對子節點的數量沒有限制。
- 在一般樹中評估任何表示式都很困難。
二叉樹
- 二叉樹最多有兩個子節點。
- 在二叉樹中評估表示式很簡單。
樹的應用
- 算術表示式的操作
- 符號表的構造
- 語法分析
- 編寫語法
- 表示式樹的建立
更新於：2020年1月8日
9K+ 瀏覽量
廣告