Chapter 6 樹狀結構 二元樹 引線二元樹 - Ian-Liu-1990/Data-Structure GitHub Wiki

１. 樹的專有名詞

  • 一般樹，不可為空

  • 祖先(ancestor): 由樹根至某節點的路徑上經過的所有節點，皆是該節點的祖先(不包含節點本身)

  • 後代(descendant): 由一節點至某樹葉的路徑上經過的所有節點，皆為該節點的後代(不包含節點本身)

  • 葉節點: 沒有子節點

  • 分支度: 某一節點(Root不代表全部節點)擁有的節點數

  • 階層(Level)[文字遊戲考題]

    1. 定義樹的世代關係,一代為一階度，此種定義樹根階層為1
    2. 定義樹根到節點的路徑長度，此種定義樹根階層為0

  • 高度(Height)[階層定義影響高度]

    • 第一種定義樹的世代關係，一代為一階度， 此種定義樹根階層為1，找樹葉節點是最大階層
    • 第二種節點到樹葉的最長路徑長度，此種定義樹根階層為0，找樹葉節點是最大階層

  • 深度(depth): 高度又稱為深度[文字遊戲]

  • 樹林: N個互斥樹組成, 移去樹根(Root)即為樹林

  • 樹的結構表示法: P6-3(Root, (Node1, Node2, ...)), 註Node1和Node2同為兄弟

２. 二元樹

  • 定義 : 有限集合，可以是一顆空的樹，非空則由樹根+左子樹，樹根，右子樹所組成，樹根+左右子樹，且左右子樹也都是二元樹．
特性 二元樹 一般樹
節點個數 0<= 1<=
排列序 有排列 無排列
分支度大小 <=2 無上限

Ａ. 二元樹特點公式，b二元樹的總分支度，ｎi代表該分之度為i的節點數

  1. b = n - 1 : 總分支度 = 總節點數 - 1
  2. ｎ = ｎ0 + ｎ1 + ｎ2 : 總節點數 = 葉子數 + 分支度為1的節點數 + 分支度為2的節點數
  3. b = ｎ1 + 2ｎ2
  4. ｎ0 = ｎ2 + 1
  5. 在第i高度上，節點數最多 2^(i-1)
  6. N個節點的二元樹，共有幾顆 : 塔卡蘭數: Ｃ(2n, n) / (n+1)

Ｃ. 完滿二元樹

  • 定義 : 高(階)度等於K，必須要等於(2^k)-1個節點數， k>=1， 此公式只適用根節點高(階)度為1

Ｄ. 完整二元樹

解: 假設樹高H，則形成完全二元樹，(2^H-1)在加1 = n，則H-1要是完滿，H-1的總節點數就是n-1，n+n-1 = 2n-1

Ｅ. 歪斜樹

Ｆ. 二元樹表示法

  • 一維陣列表示法 : 重要
  • 鏈結串列表示法 : 重要

Ｇ. 二元樹的追蹤

  • 中序:左子樹->樹根->右子樹
void inorder(Node_type *tree){
    if( tree != Null){
       inorder(tree->Llink);
       printf("%d", tree->data);
       inorder(tree->RLink);
    }
}
  • 前序:樹根->左子樹->右子樹
void preorder(Node_type *tree){
    if(tree != null){
    printf("%d", tree->data);
    preorder(tree->Llink);
    preorder(tree->Rlink);
    }
}
  • 後序:左子樹->右子樹->樹根
void postorder(Node_type *tree)
{
    if(tree != Null){
    postorder(tree->Llink);
    postorder(tree->Rlink);
    printf("%d", tree->data);
   }
}

Ｈ. 引線二元樹

LBIT0/1 LLINK DATA RLINK RBIT0/1

Ｉ. 一般樹轉二元樹

Ｊ. 森林轉二元樹

序列轉二元樹

步驟演算法

決定唯一的二元樹

  • 給中序+前序 推 後序
  • 給中序+後序 推 前序

算式樹 - 可以出的很難