樹的定義和性質

樹是一種離散結構，表示各個元素或節點之間的層次關係。其中父節點最多隻有兩個子節點的樹稱為二叉樹。

樹及其性質

定義 − 樹是一個連通的無環無向圖。圖G中每對頂點之間都存在一條唯一的路徑。具有N個頂點的樹包含(N-1)條邊。度為0的頂點稱為樹的根。度為1的頂點稱為樹的葉子節點，內部節點的度至少為2。

示例 − 下面是一個樹的示例：

Tree

樹的中心和雙中心

樹的中心是偏心率最小的頂點。樹G中頂點X的偏心率是頂點X與樹的任何其他頂點之間的最大距離。最大偏心率是樹的直徑。如果一棵樹只有一箇中心，則稱為中心樹；如果一棵樹有多箇中心，則稱為雙中心樹。每棵樹要麼是中心樹，要麼是雙中心樹。

帶標籤的樹

定義 − 帶標籤的樹是指其頂點被分配了從1到n的唯一編號的樹。我們可以手動計算n較小值時的此類樹的數量，以便推測一個通用公式。具有n個頂點的帶標籤樹的數量是nn-2。如果兩個帶標籤樹的圖是同構的，並且兩棵樹的對應點具有相同的標籤，則這兩個帶標籤的樹是同構的。

示例

A labeled tree with two verticesThree possible labeled tree with three vertices

無標籤樹

定義 − 無標籤樹是指其頂點未分配任何編號的樹。具有n個頂點的無標籤樹的數量是$\frac {(2n)!}{ (n+1)!n! }$（第n個卡塔蘭數）

示例

An unlabeled treeAn unlabeled tree with three verticesTwo possible unlabeled trees with four vertices

有根樹

有根樹G是一個連通的無環圖，它有一個特殊的節點，稱為樹的根，並且每條邊都直接或間接地起源於根。有序有根樹是有根樹，其中每個內部頂點的子節點都是有序的。如果一個有根樹的每個內部頂點最多有m個子節點，則它被稱為m叉樹。如果一個有根樹的每個內部頂點恰好有m個子節點，則它被稱為滿m叉樹。如果m = 2，則有根樹稱為二叉樹。

A Rooted Tree

二叉搜尋樹

二叉搜尋樹是一種滿足以下性質的二叉樹：

  • 頂點V的左子樹中的X，Value(X) ≤ Value (V)
  • 頂點V的右子樹中的Y，Value(Y) ≥ Value (V)

因此，內部節點V的左子樹的所有頂點的值都小於或等於V，而內部節點V的右子樹的所有頂點的值都大於或等於V。從根節點到最深節點的連結數量是二叉搜尋樹的高度。

示例

Binary Search Tree

在BST中搜索鍵的演算法

BST_Search(x, k)
if ( x = NIL or k = Value[x] )
   return x;
if ( k < Value[x])
   return BST_Search (left[x], k);
else
   return BST_Search (right[x], k)

二叉搜尋樹的複雜度


平均情況最壞情況
空間複雜度O(n)O(n)
搜尋複雜度O(log n)O(n)
插入複雜度O(log n)O(n)
刪除複雜度O(log n)O(n)

更新於：2019年8月23日

14K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告