樹的定義

一種存資料的型態，由最初的節點延伸下多個分支，每個分支都個有個自的子分支，分支下可分割成彼此不相交的子集合，也稱為子樹。

樹的專門術語

• 根結點:最初的節點(A)
• 階層:樹中的子分層樹(E的層次為3，樹的高度是4)
• 節點:分支下所連接的空間(B,C,D......)
• 父節點:節點的上一個節點(B是D的父節點)
• 兄弟:在同一個分支層，且有同一個父節點(D,E為兄弟)
• 祖先,兄弟:子分支與子分支源的關係(I的祖先為A,C,H，C的祖先為F,G,H,I)
• 終端節點(樹葉):最末端沒有分支的節點(E,F)
• 內部節點:非終端節點(A,B,C,H)
• 分支度:分支的數量(B的分支度數量為2,數的分支度為3)
  

樹的表示法

• 串列:在非完滿樹中，會有浪費空間的缺點
• 左小孩右兄弟:將每個小孩節點放到左邊，兄弟節點放到右邊，

二元樹

由一個跟節點和兩個分支構成的樹，兩個分支一位置被稱為左子樹與右子樹，樹不可為空集合，二元樹可以，且有順序之分。

特殊形態的二元樹

• 歪斜二元樹:皆為子節點的二元樹
• 完全二元樹:每個分支的子節點樹皆為二或零
• 完滿二元樹:每個分之的子節點節樹為二，深度為k的時候，節點為(2^K)-1

二元樹的性質

• 二元樹的最大節點數為 (2^K)-1，深度為K時

二元樹的表示法

先略

二元樹的追蹤

    左兒子 資料 右兒子
      L    V    R

依照追蹤組合有六種:LVR、LRV、VLR、VRL、RVL、RLV
因追蹤有受先左再右，因此剩3種:LVR 、 LRV 、 VLR

• 中序
• 

void inorder(tree_pointer ptr)
/*中序追蹤 */
{
    if (ptr) {
L     inorder(ptr->left_child);       
V     printf(“%d”, ptr->data);      
R     inorder(ptr->right_child);  
    }
}

• 前序
  

void preorder(tree_pointer ptr)
/* 前序追蹤 */
{
     if (ptr) {
V       printf(“%d”, ptr->data); 
L       preorder(ptr->left_child);       
R       preorder(ptr->right_child);  
     }
}

• 後序
  

void postorder(tree_pointer ptr)
/* 後序追蹤 */
{
    if (ptr) {
L      postorder(ptr->left_child);       
R      postorder(ptr->right_child);  
V      printf(“%d”, ptr->data);
    }
}

• 疊代(中序)
  利用疊代的方式作中序追蹤

void iter_inorder(tree_pointer node)
{
  int top= -1; /* 初始化堆疊 */
  tree_pointer stack[MAX_STACK_SIZE];
  for (;;) {
     for (; node; node = node->left_child)
         push(node);  /* 將節點加入堆疊 */
     node= pop();  /* 自堆疊刪除節點 */
     if (!node) break;  /* 空堆疊 */
     printf(“%d”, node->data);
     node = node->right_child;
  }
}

• 階序
  

void level_order(tree_pointer ptr)
/* 階層次序追蹤 */
{
    int front = rear = 0;
    tree_pointer queue[MAX_QUEUE_SIZE];
    if (!ptr) return;   /* 空樹 */
    addq(ptr);
    for (;;) {
        ptr = deleteq();
        if (ptr) {
        printf (“%d”, ptr ->data);
        if (ptr ->left_child)
            addq(ptr ->left_child);
        if (ptr ->right_child)
            addq(ptr ->right_child);
        }
        else break;
    }
}