kiniku
Binary Tree

Photo by niko photos on Unsplash

Binary Tree

kiniku's photo
kiniku
·

5 min read

樹狀結構就像以下圖片的樣子，是一種有階層架構的非線性資料集合

一般的樹狀結構擁有以下的特徵：

  1. 節點：代表某項資料

    1. 根結點：沒有父節點的節點，一顆樹也只能有一個根結點

    2. 父節點、子節點：若某個節點連接到下面一個節點，則該節點為父節點，而下面的節點稱為子節點

    3. 祖先節點、子孫節點：若某個節點有一條路徑可以通往另一個節點，那就代表該節點為祖先節點

    4. 兄弟節點：當它們都是同一個父節點的子節點時則該子節點們互為兄弟節點

    5. 樹葉節點：分支度為0的節點

  2. 分支度：一個節點有幾個子節點稱為分支度

  3. 高度：某節點到距離最遠的樹葉節點的最長路徑

  4. 深度：根節點到某節點的路徑長度

  5. 階度：樹中結點世代的關係

樹的表示法

如果一般樹使用鏈結串列來表示的話，會因為最大節點的數量而決定要多少個鏈結，可是這樣就會導致空間上的浪費，因為不是每個節點都有最大數量的子節點

像上面的圖片，最大數量就是3，可是其他節點的子節點就只有2而已，所以每個節點都還會再浪費一個鏈結空間，樹葉節點還會再浪費更多的空間

所以通常會用另外一種方法Left Child-Right Sibling，把多元樹轉換成二元樹，這樣可以節省空間，但缺點是操作會比一般的樹還要花更多的時間，所以通常會使用的場合是，記憶體非常少又或是不需要隨機訪問的時候

二元樹

二元樹的意思就是每個節點最多只有兩個子節點而已，而他和一般樹的差別在於二元樹有排列順序關係，而且二元樹可以是空的，那會用到二元樹是因為二元樹浪費的空間比起其他的一般樹還要少，所以基本上都會使用二元樹。下面有著3個比較特殊的二元樹種類：

  1. $$歪斜樹：如果歪斜樹完全沒有左節點或右節點的話，就稱為歪斜樹$$

  2. $$完滿二元樹：如果有一棵二元樹的高度為k，那麼樹的節點數為2^k - 1$$

  3. $$完整二元樹：如果有一棵二元樹的高度為k，那麼樹的節點數少於2^k - 1$$

二元樹的表示法

而二元樹的儲存方式也分為陣列和鏈結串列，但是如果用陣列儲存的話可能會發生空間上的浪費，不過如果是完整二元樹或完滿二元樹的話，因為是按照陣列的順序排列的，所以不會有跳號的問題，相對地說陣列不適合用於歪斜樹

鏈結串列方式就比較適合二元樹，加入和刪除就會比較容易，尤其是當二元樹是不完整的，但是會比較難找到父節點

我們也可以用動態的方式建立二元樹，透過提供的字串來建立，因為二元樹只有兩個子節點，所以字串可以寫成R(A...)(B...)，利用兩個括號來代表左子樹及右子樹

二元樹走訪

二元樹走訪也就是說把樹中的每個節點都走訪過一次，並且都是從左到右的話，可以分為三種遍歷方式：

  1. 前序走訪：先印出root節點然後才印出左子節點及右子節點，如果比起其他的節點需要先印出root節點的話，可以使用前序走訪

    使用堆疊來完成前序走訪的話，會先把root的左子節點都先push進堆疊裡並且印出，之後再判斷該節點是否指向空的位址，如果是的話就把堆疊裡的top節點給pop，然後在檢查是否有右子節點

  2. 中序走訪：會先走訪左子樹之後拜訪根節點之後走訪右子樹，如果樹有固定的排序的話，可以使用中序走訪，來印出原本的內容

    使用堆疊來完成中序走訪的話，會先把root的左子節點都先push進堆疊裡，之後再判斷該節點是否指向空的位址，如果是的話就把堆疊裡的top節點給pop，然後在檢查是否有右子節點

  3. 後序走訪：先從左至右才印出root節點，如果需要先印出樹葉節點的話，可以使用後序走訪

圓圈裡的值為遍歷的順序，而外面的才是儲存的值

還有一個叫做level order的遍歷方式，依照階層來印出值

二元運算樹

運算式可以用二元樹來儲存，二元運算樹的前中後序，就代表運算式的前中後序。可以使用括號來逐步變成二元運算樹，會先由內部的括號開始，然後左邊運算元做為左子節點，又變運算元做為右子節點。

引線二元樹

引線二元樹就是把原本沒利用到的空節點加以利用，把這些空節點轉換成引線指向其他節點，其好處是中序遍歷時不需用遞迴跟堆疊

引線二元樹跟二元樹最大的差別在於，引線二元樹多了兩個欄位，去判斷是否為引線

insert()

透過比對值的大小來判斷要插入左邊還是右邊，並且插入在樹葉節點的位置

deleteNode()

先判斷父節點是否為root，接著再判斷要刪除的節點是在父節點的左邊還是右邊

當要刪除兩個子節點時，先尋找中序前行者之後，改變該節點的右節點，最後在判斷該節點是在父節點的左邊還是右邊來連接

刪除只有一個子節點時，要先判斷該節點是在父節點的左邊還是右邊，接著再判斷要刪除的節點有多少個子節點還是樹葉節點。如果父節點就是root的話，就一樣判斷是在左邊還是右邊，如果是左邊的話要尋找中序前行者，右邊的話要尋找中序後繼者

完整程式碼

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

struct tbintree {
    int number;
    int rbit;
    int lbit;
    struct tbintree* lchild;
    struct tbintree* rchild;
} *root, * ptr, * newnode;

struct tbintree* newtbintree();
void insert();
void deleteNode();
void inorderShow(struct tbintree*);
void insertRight(struct tbintree*, struct tbintree*);
void insertLeft(struct tbintree*, struct tbintree*);
struct tbintree* insucc(struct tbintree*);
struct tbintree* inpred(struct tbintree*);
void preorderShow(struct tbintree*);
struct tbintree* preordersucc(struct tbintree*);

int main()
{
    const char* menuPrompt =
        "=== Thread Binary Search Program ==\n"
        "  1. Insert\n"
        "  2. Delete\n"
        "  3. Show\n"
        "  4. PreShow\n"
        "  5. Quit\n"
        "Enter your choice: ";
    int choice;
    root = newtbintree();
    root->lchild = root;
    root->rchild = root;
    root->lbit = 0;
    root->rbit = 1;
    do {
        printf("\n%s", menuPrompt);
        scanf_s("%d", &choice);
        switch (choice) {
        case 1:
            insert();
            break;
        case 2:
            deleteNode();
            break;
        case 3:
            inorderShow(root);
            break;
        case 4:
            preorderShow(root);
            break;
        case 5:
            puts("Bye Bye ^_^");
            exit(1);
        default:
            puts("Invalid choice !!");
        }
    } while (1);
    printf("\n");
    return 0;
}

void insert()
{
    newnode = newtbintree();
    printf("\nEnter a number to insert : ");
    scanf_s("%d", &newnode->number);
    if (root->lchild == root) {
        insertLeft(root, newnode);
        printf("Node %d has been inserted!\n", newnode->number);
    }
    else {
        ptr = root->lchild;
        while (ptr->number != newnode->number) {
            if (newnode->number < ptr->number) {
                if (ptr->lbit == 0) {
                    insertLeft(ptr, newnode);
                    break;
                }
                else
                    ptr = ptr->lchild;
            }
            else if (newnode->number > ptr->number) {
                if (ptr->rbit == 0) {
                    insertRight(ptr, newnode);
                    break;
                }
                else
                    ptr = ptr->rchild;
            }
        }
        if (ptr->number == newnode->number) {
            puts("Number existed ...!");
            return;
        }
        else
            printf("Node %d has been inserted!\n", newnode->number);
    }
}

void deleteNode()
{
    struct tbintree* ptrParent;
    struct tbintree* ptrPred;
    struct tbintree* ptrSucc;
    int num;

    if (root->lchild == root) {
        puts("No Data!");
        return;
    }
    printf("Enter a number u want to delete: ");
    scanf_s("%d", &num);
    ptrParent = root;
    ptr = root->lchild;
    while (ptr->number != num) {
        ptrParent = ptr;
        if (num < ptr->number) {
            if (ptr->lbit == 1)
                ptr = ptr->lchild;
            else 
                break;
        }
        else if (num > ptr->number) {
            if (ptr->rbit == 1)
                ptr = ptr->rchild;
            else
                break;
        }
    }
    if (ptr->number != num) {
        printf("Not found number %d!\n", num);
        return;
    }
    printf("Deleting number %d... OK!\n", ptr->number);

    if (ptr->lbit == 0 && ptr->rbit == 0) {
        if (ptrParent == root) {
            ptrParent->lchild = root;
            ptrParent->lbit = 0;
        }
        else if (ptr->number < ptrParent->number) {
            ptrParent->lchild = ptr->lchild;
            ptrParent->lbit = 0;
        }
        else {
            ptrParent->rchild = ptr->rchild;
            ptrParent->rbit = 0;
        }
        free(ptr);
    }
    else if (ptr->lbit == 1 && ptr->rbit == 1) {
        ptrPred = inpred(ptr);
        ptrPred->rchild = ptr->rchild;
        ptrPred->rbit = ptr->rbit;
        if (ptrParent->lbit == 1)
        {
            ptrParent->lchild = ptr->lchild;
        }
        else
        {
            ptrParent->rchild = ptr->lchild;
        }
        free(ptr);
    }
    else 
    {
        if (ptrParent == root) 
        {
            if (ptr->lbit == 1)
            {
                ptrPred = inpred(ptr);
                root->lchild = ptr->lchild;
                ptrPred->rchild = root;
            }
            else 
            {
                ptrSucc = insucc(ptr);
                root->lchild = ptr->rchild;
                ptrSucc->lchild = root;
            }
        }
        else 
        {
            if (ptr->number < ptrParent->number) 
            {
                if (ptr->rbit == 1 && ptr->lbit == 0) 
                {
                    ptr->rchild->lchild = ptr->lchild;
                    ptr->rchild->lbit = ptr->lbit;
                    ptrParent->lchild = ptr->rchild;
                    ptrParent->lbit = ptr->rbit;
                }
                else if (ptr->rbit == 0 && ptr->lbit == 1)
                {
                    ptr->lchild->rchild = ptr->rchild;
                    ptr->lchild->rbit = ptr->rbit;
                    ptrParent->lchild = ptr->lchild;
                    ptrParent->lbit = ptr->lbit;
                }
            }
            else 
            {
                if (ptr->lbit == 1 && ptr->rbit == 0) 
                {
                    ptrParent->rchild = ptr->lchild;
                    ptrParent->rbit = ptr->lbit;
                    ptr->lchild->rchild = ptr->rchild;
                    ptr->lchild->rbit = ptr->rbit;
                }
                else if (ptr->lbit == 0 && ptr->rbit == 1) 
                {
                    ptrParent->rchild = ptr->rchild;
                    ptrParent->rbit = ptr->rbit;
                    ptr->rchild->lchild = ptrParent;
                    ptr->rchild->lbit = ptr->lbit;
                }
            }
            free(ptr);
        }
    }
}

void insertRight(struct tbintree* nodeParent, struct tbintree* node)
{
    struct tbintree* w;
    node->rchild = nodeParent->rchild;
    node->rbit = nodeParent->rbit;
    node->lchild = nodeParent;
    node->lbit = 0;
    nodeParent->rchild = node;
    nodeParent->rbit = 1;
    if (node->rbit == 1) {
        w = insucc(node);
        w->lchild = node;
    }
}

void insertLeft(struct tbintree* nodeParent, struct tbintree* node)
{
    struct tbintree* w;
    node->lchild = nodeParent->lchild;
    node->lbit = nodeParent->lbit;
    node->rchild = nodeParent;
    node->rbit = 0;
    nodeParent->lchild = node;
    nodeParent->lbit = 1;
    if (node->lbit == 1) {
        w = inpred(node);
        w->rchild = node;
    }
}

struct tbintree* preordersucc(struct tbintree* node) {
    struct tbintree* position;
    if (node->lbit == 1)
    {
        return node->lchild;
    }
    else
    {
        position = node;
        while (position->rbit == 0)
        {
            position = position->rchild;
        }
        return position->rchild;
    }
}

void preorderShow(struct tbintree* node) {
    struct tbintree* p = root;
    if (node->lchild == root) {
        puts("No Data!");
        return;
    }
    puts("\nPreorder display thread binary search tree");
    do
    {
        p = preordersucc(p);
        if (p != root)
            printf("%-5d", p->number);
    } while (p != root);
    puts("\n--------------------------------------------");
}

void inorderShow(struct tbintree* node)
{
    if (node->lchild == root) {
        puts("No Data!");
        return;
    }
    puts("\nInorder display thread binary search tree");
    ptr = root;
    do {
        ptr = insucc(ptr);
        if (ptr != root)
            printf("%-5d", ptr->number);
    } while (ptr != root);
    puts("\n--------------------------------------------");
}

struct tbintree* insucc(struct tbintree* node)
{
    struct tbintree* succ;
    succ = node->rchild;
    if (node->rbit == 1)
        while (succ->lbit == 1)
            succ = succ->lchild;
    return succ;
}

struct tbintree* inpred(struct tbintree* node)
{
    struct tbintree* pred;
    pred = node->lchild;
    if (node->lbit == 1)
        while (pred->rbit == 1) 
            pred = pred->rchild;
    return pred;
}

struct tbintree* newtbintree()
{
    struct tbintree* temp;
    temp = (struct tbintree*)malloc(sizeof(struct tbintree));
    temp->lchild = NULL;
    temp->rchild = NULL;
    return temp;
}
BinaryTrees