線索二叉樹的構造及前驅后繼的查找

在本文中，我將介紹三種線索二叉樹的構造方法，包括中序線索二叉樹、先序線索二叉樹以及后序線索二叉樹，在介紹程序中，首先我會給出構造的基本思路，然后說明其中幾點注意事項，最后我將給出代碼示例，之后，我會針對每一種線索二叉樹，給出其查找某節點p的前驅和后繼結點的方法，最后我將做一個小小的對比總結，以便清楚地展現出不同線索二叉樹在構造程序中以及查找前驅后繼結點上的區別，

下面我們就開始吧！

1. 二叉樹的線索化

1.1 中序線索二叉樹

中序線索二叉樹的定義： 一個二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指標改為指向該節點在中序序列中的后繼，所有原本為空的左(孩子)指標改為指向該節點的中序序列的前驅，

1.1.1 樸素方法找中序前驅和后繼

首先我們來思考如何用一種簡單的方法來尋找中序遍歷中某個結點的前驅和后繼呢？

我們在遍歷二叉樹的時候，總是依次獲取后繼結點的，那么我們就不難想到，我們只要能夠在遍歷的程序中不斷記錄當前結點的前一個結點，那么就能夠很方便的找到目標結點的前驅結點，為此只需額外設定一個pre指標來記錄當前結點的前一個結點即可，下圖給出了這個思想的示例：

當指標q和目標結點p重合時，pre指標指向的結點即為目標結點的前驅結點，當然，利用這種方法我們也可以找到目標結點的后繼結點，只需要讓pre指標與p指標重合，此時q指標指向的就是后繼結點（但是需要對最后一個結點的后繼結點進行特殊處理），

代碼：

void findPre(BiTree T) {
    if (T == NULL) {
        return;
    }
    findPre(T -> lchild);
    visit(T);
    findPre(T -> rchild);
}

void visit(BiTNode *q) {
    if (q == p) {
        final = pre;
    } else {
        pre = q;
    }
}

BiTNode *p; // p指向目標結點
BiTNode *pre = NULL; // 指向當前結點的前驅結點
BiTNode *final = NULL; // 記錄最終結果

1.1.2 中序線索化

中序線索化的基本思想： 本質上就是借助1.1.1的思想，借助pre指標來記錄前一個結點，若當前結點p的左孩子為空，則讓其左指標指向pre使其成為前驅線索(需要借助ltag=1進行標記)，若pre指向的結點的右孩子為空，則讓其右指標指向當前結點p使其成為后繼線索(需要借助rtag=1進行標記)，

注意事項：

• pre引數需要是參考型別，因為在程式運行中，pre的指向在不斷進行更新，
• 處理中序遍歷的最后一個結點時，可以不用判斷rchild是否為NULL，因為中序遍歷的最后一個結點的rchild必然為NULL否則就會繼續遍歷下去，但是，為了和其他線索二叉樹統一起來，建議對最后一個結點進行一個非空判斷，

代碼：

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode, *ThreadTree;

void InThread(ThreadTree p, ThreadTree &pre) {
    if (p == NULL) return;
    InThread(p->lchild, pre); // 遞回線索化左子樹
    if (p->lchild == NULL) { // 左子樹為空，建立前驅線索
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) { // 建立前驅結點的后繼線索
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
    InThread(p->rchild, pre); // 遞回線索化右子樹
}

void CreatInThread(ThreadTree T) {
    ThreadNode *pre = NULL;
    if (T != NULL) {
        InThread(T, pre);
        if (pre->rchild == NULL) { // 處理最后一個結點
            pre->rtag = 1;
        }
    }
}

1.2 先序線索二叉樹

先序線索二叉樹的定義： 一個二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指標改為指向該節點在先序序列中的后繼，所有原本為空的左(孩子)指標改為指向該節點的先序序列的前驅，

1.2.1 先序線索化

先序線索化的基本思想與中序線索化的思想相同，在這里不做過多贅述，

注意事項：

• 先序線索化程序中有一個需要格外注意的問題就是“轉圈”問題，如下圖所示的情況：當對d結點的左孩子線索化之后，由于先序遍歷的規則，我們接下來應該遍歷的是d的左子樹也就是b，這樣就導致了“轉圈”問題，為了避免這個問題，我們就需要借助ltag判斷左孩子是否為前驅線索，

• 處理先序遍歷的最后一個結點時，其實也可以不用判斷rchild是否為NULL，因為先序遍歷的最后一個結點的rchild必然為NULL否則就會繼續遍歷下去，

  

代碼：

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode, *ThreadTree;

void PreThread(ThreadTree p, ThreadTree &pre) {
    if (p == NULL) return;
    if (p->lchild == NULL) { // 左子樹為空，建立前驅線索
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) { // 建立前驅結點的后繼線索
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
    if (p -> ltag == 0) { // 避免轉圈問題
        PreThread(p->lchild, pre); // 遞回線索化左子樹
    }
    PreThread(p->rchild, pre); // 遞回線索化右子樹
}

void CreatPreThread(ThreadTree T) {
    ThreadNode *pre = NULL;
    if (T != NULL) {
        PreThread(T, pre);
        if (pre->rchild == NULL) { // 處理最后一個結點
            pre->rtag = 1;
        }
    }
}

1.3 后序線索二叉樹

后序線索二叉樹的定義： 一個二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指標改為指向該節點在后序序列中的后繼，所有原本為空的左(孩子)指標改為指向該節點的后序序列的前驅，

1.3.1 后序線索化

后序線索化的基本思想與中序線索化的思想相同，在這里不做過多贅述，

注意事項：

• 后序線索化程序中不會出現“轉圈”問題
• 但是，處理后序遍歷的最后一個結點時，需要進行額外的判斷，確定最后一個結點的右孩子是否為空，

代碼：

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode, *ThreadTree;

void PostThread(ThreadTree p, ThreadTree &pre) {
    if (p == NULL) return;
    PostThread(p->lchild, pre); // 遞回線索化左子樹
    PostThread(p->rchild, pre); // 遞回線索化右子樹
    if (p->lchild == NULL) { // 左子樹為空，建立前驅線索
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) { // 建立前驅結點的后繼線索
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
}

void CreatPreThread(ThreadTree T) {
    ThreadNode *pre = NULL;
    if (T != NULL) {
        PostThread(T, pre);
        if (pre->rchild == NULL) { // 處理最后一個結點
            pre->rtag = 1;
        }
    }
}

2. 線索二叉樹找前驅/后繼

2.1 中序線索二叉樹找后繼

在中序線索二叉樹中找到指定結點p的中序后繼next

1. 若p->rtag==1，則next=p->rchild

2. 若p->rtag==0，則說明p一定有右孩子，此時next=p的右子樹中最左下結點

   

代碼：

ThreadNode *Firstnode(ThreadNode *p) { // 找最左下結點
    while (p -> ltag == 0) {
        p = p -> lchild;
    }
    return p;
}

ThreadNode *Nextnode(ThreadNode *p) { // 判斷p是否有右子樹
    if (p -> rtag == 0) {
        return Firstnode(p -> rchild);
    } else {
        return p -> rchild;
    }
}

void InOrder(ThreadNode *T) { // 利用線索二叉樹實作非遞回的中序遍歷
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {
        visit(p);
    }
}

2.2 中序線索二叉樹找前驅

在中序線索二叉樹中找到指定結點p的中序前驅pre

1. 若p->ltag==1，則pre=p->lchild

2. 若p->ltag==0，則說明p一定有左孩子，此時pre=p的左子樹中最右下結點

   

代碼：

ThreadNode *Lastnode(ThreadNode *p) { // 找最左下結點
    while (p -> rtag == 0) {
        p = p -> rchild;
    }
    return p;
}

ThreadNode *Prenode(ThreadNode *p) { // 判斷p是否有右子樹
    if (p -> ltag == 0) {
        return Lastnode(p -> lchild);
    } else {
        return p -> lchild;
    }
}

void RevInOrder(ThreadNode *T) { // 利用線索二叉樹實作非遞回的逆向中序遍歷
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) {
        visit(p);
    }
}

2.3 先序線索二叉樹找后繼

在先序線索二叉樹中找到指定結點p的先序后繼next

1. 若p->rtag==1，則next=p->rchild

2. 若p->rtag==0，則說明p一定有右孩子，此時又分為兩種情況：

   1. 若p有左孩子，則next=p->lchild
   2. 若p沒有左孩子，則next=p->rchild
   

代碼：

ThreadNode *Nextnode(ThreadNode *p) {
    if (p -> rtag == 1) {
        return p -> rchild;
    } else if (p -> rtag == 0 && p -> ltag == 0) {
        return p -> lchild;
    } else if (p -> rtag == 0 && p -> ltag == 1) {
        return p -> rchild;
    }
}

2.4 先序線索二叉樹找前驅

在先序線索二叉樹中找到指定結點p的先序前驅pre

1. 若p->ltag==1，則pre=p->lchild

2. 若p->ltag==0，由于先序遍歷的特性，p的左右子樹不可能為其先序前驅，且先序前驅只可能存在于上層結點中，因此普通的二叉鏈表除非從頭遍歷否則是無法找到其先序前驅的，我們需要借助三叉鏈表才能實作，

   
   對情況3的額外說明
   

2.5 后序線索二叉樹找后繼

在后序線索二叉樹中找到指定結點p的后序后繼next

1. 若p->rtag==1，則next=p->rchild

2. 若p->rtag==0，由于后序遍歷的特性，p的左右子樹不可能為其后序后繼，且后序后后繼只可能存在于上層結點中，因此普通的二叉鏈表除非從頭遍歷否則是無法找到其后序后繼的，我們需要借助三叉鏈表才能實作，

   
   對情況3的額外說明
   

?

2.6 后序線索二叉樹找前驅

在后序線索二叉樹中找到指定結點p的后序前驅pre

1. 若p->ltag==1，則pre=p->lchild

2. 若p->ltag==0，則說明p一定有左孩子，此時又分為兩種情況：

   1. 若p有右孩子，則next=p->rchild
   2. 若p沒有右孩子，則next=p->lchild
   

3. 小結

標籤：其他

上一篇：E104-BT01超低功耗藍牙模塊BLE4.0協議的片載系統解決方案

下一篇：【Unity TIL】在 android 下使用 TouchScreenKeyboard 進行輸入（一）