iT邦幫忙

0

【資料結構】樹(1/3)預習

c

樹的定義

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

樹的專門術語

  • 根結點:最初的節點(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;
    }
}

尚未有邦友留言

立即登入留言