雙親表示法詳解

一、雙親表示法簡介

雙親表示法，簡稱為「樹」，是一種在計算機科學和數學中廣泛使用的數據結構。它由節點和邊組成，通常用於模擬具有層次結構的問題。與其他數據結構相比，樹結構具有更高的搜索效率和更好的可讀性，因此在資料庫、圖形建模、編譯器等領域都得到了廣泛的應用。

在雙親表示法中，每個節點都有一個指向其父節點的指針，並且每個節點最多只有一個父節點。根據節點之間的關係，樹結構可以被分為有根樹和無根樹兩種類型。在有根樹中，一個節點只有一個入度，而在無根樹中，節點沒有入度限制。

二、雙親表示法的基本操作

1、創建樹

//創建樹的結構體
typedef struct{
    int data; //節點的數據
    int parent; //指向其父節點的指針
}TreeNode;
 
//創建樹的函數
void createTree(TreeNode t[], int n){
    int i, j, k;
    for (i=0; i<n; i++){
        printf("請輸入第%d個節點的數據和雙親編號：", i+1);
        scanf("%d%d", &t[i].data, &t[i].parent);
        for (j=0; j<i; j++){  //判斷是否重複輸入
            if(t[i].data==t[j].data){
                printf("輸入的節點已存在，請重新輸入！\n");
                i--;
                break;
            }
        }
        if(t[i].parent!=i-1){  //判斷是否滿足雙親表示法的條件
            printf("輸入的雙親編號錯誤，請重新輸入！\n");
            i--;
        }
    }
}

在創建樹的過程中，我們利用結構體TreeNode來存儲樹節點的數據和它的雙親編號。對於每個節點，我們用scanf函數獲取輸入的數據和雙親編號，並與之前輸入的節點進行比較，以確保輸入的節點沒有重複。在輸入完成後，我們再次遍歷所有節點，判斷它們的雙親編號是否符合雙親表示法的條件，即是否等於它的編號減一。

2、遍歷樹

//先序遍歷
void preOrder(TreeNode t[], int n, int root){
    int i;
    printf("%d ", t[root].data); //輸出根節點
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //遍歷其子節點
            preOrder(t, n, i);
        }
    }
}
 
//後序遍歷
void postOrder(TreeNode t[], int n, int root){
    int i;
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //遍歷其子節點
            postOrder(t, n, i);
        }
    }
    printf("%d ", t[root].data); //輸出根節點
}

遍歷樹的過程就是按照一定的順序遍歷樹的所有節點。在雙親表示法中，我們可以使用遞歸的方式遍歷樹結構。對於每個節點，我們判斷它是否為根節點，然後遍歷它的子節點，直到遍歷到葉子節點為止。

3、判斷是否為葉子節點

bool isLeaf(TreeNode t[], int n, int root){
    int i;
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //如果有子節點，則不是葉子節點
            return false;
        }
    }
    return true; //沒有子節點，則是葉子節點
}

葉子節點是指沒有子節點的節點。在雙親表示法中，我們可以通過判斷一個節點是否有子節點來判斷它是否為葉子節點。

三、雙親表示法的應用場景

1、資料庫中的樹結構

資料庫中的樹結構是一種用於描述數據之間層次關係的常見數據結構，通常用於表示各種分類結構。例如，一本圖書可以用樹的形式表達為作者->出版社->書名，一個公司可以用樹的形式表達為公司->部門->員工。使用雙親表示法存儲樹結構可以使得訪問父節點更加容易。

2、語法分析器中的樹結構

編譯器中的語法分析器通常使用樹結構來表示程序的語法結構。雙親表示法可以方便地表示每個語法構造所在的上下文，使得錯誤處理和代碼生成更加容易。

3、圖形建模中的樹結構

在圖形建模中，雙親表示法可以用於表示三維物體的層次結構，從而方便地實現平移、旋轉和縮放等操作。

4、面向對象中的繼承關係

在面向對象的編程語言中，繼承關係可以用樹結構來表示，子類可以看作是父類的子節點。使用雙親表示法可以很方便地查找和處理繼承層次結構。