Next Nest

wusa!~(•㉨•)

二叉樹筆記 I 基礎構造

发表于 Valine：

二叉樹的概念等基礎知識大部分已在離散數學中學過，在此不再重複或贅述。

Basic Construction

C++
1
2
3
4
5
6
struct Node {
    int val; // 亦可以其他數據類型，只需把`int`替換爲`float`或`char`等
    struct Node *parent; // 指向母親節點的指針
    struct Node *lchild; // 指向左女兒的指針
    struct Node *rchild; // 指向右女兒的指針
};

爲了方便構造，我們使用向指針分配動態内存的形式來構造節點，申請方法很簡單，只需要

C++
1
struct Node * newnode = (struct Node *)malloc(sizeof(struct Node));

即可向名爲newnode的節點指針分配一個節點所需要的空間。

對於某一個節點所不具有的成分，我們讓指向該成分的指針指空，
例如在剛剛構造的時候，我們往往不知道它的左右女兒是誰，此時就讓它的左右女兒皆指空

C++
1
2
newnode->lchild = nullptr;
newnode->rchild = nullptr;

又如對於沒有母親節點的根節點，其母親指針亦作指控處理，我們在構造之時往往操作如下

C++
1
root->parent = nullptr;

但是對於其他的節點，則需要設置它的母親節點，並在它的母親節點上設置左女兒或有女兒，
例如新節點newnode是節點herparent的左女兒，則操作如下

C++
1
2
newnode->parent = herparent;
herparent->lchild = newnode;

以此建立雙向連接，右女兒同理，只需要把lchild替換爲rchild。

根據離散數學中的相關知識，二叉樹1中的節點可以分爲根(root)、莖、葉(leaf)，這三種節點。其中

  • 根：沒有母親的節點（這個描述聼上去怎麽那麽像在罵人x
  • 葉：沒有女兒的節點
  • 其他的既不是根亦不是葉，它們都既有母親亦有女兒

此外，對於某些莖而言，它僅僅具有左子樹或右子樹，此時它的右女兒或左女兒指針指空。

至此，二叉樹的基本構造方法已講解完畢，下面會附贈一個實例，希望能有助於大家理解。

Example

構造二叉樹如下

root: 39 (根節點)
     /
    7
     \
      128

  • 如圖所示，根節點的值為39，其含有一個左女兒，值為7，該節點含有一個葉子作爲右女兒，其值為128

  • 解

    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>

    using namespace std;
    using namespace __gnu_cxx;

    struct Node {
        int val;
        struct Node *parent, *lchild, *rchild;
    } *root, *node0, *node1;

    int main(int argc, char *argv[]) {
        // 構造根節點，其值爲 39
        root = (struct Node *)malloc(sizeof(struct Node));
        root->val = 39;
        root->parent = nullptr; // 由於根節點沒有母親節點，所以母親指針指空
        root->lchild = nullptr; // 左右女兒待定，指空
        root->rchild = nullptr;

        // 構造根節點的左女兒，其值爲 7
        node0 = (struct Node *)malloc(sizeof(struct Node));
        node0->val = 7;
        node0->parent = root; // 它是根節點的左女兒，
                              //  但必須先聲明它本身的母親是根節點
        node0->lchild = nullptr;
        node0->rchild = nullptr;
        /**
         * 筆者個人認爲這裏需要多説一點
         *  剛才在設置根節點和 node0 的時候，統一把左右女兒皆進行指空處理
         *   即 root->lchild = root->rchild = nullptr;
         *   與 node0->lchild = node0->rchild = nullptr;
         *  這樣做背後的道理便是，在構造時刻，先假設它是一片葉子，
         *  如若還有女兒的話，再往上添加，像下面這一步
         */
        root->lchild = node0;

        // 構造該節點的右女兒，其值爲 128
        node1 = (struct Node *)malloc(sizeof(struct Node));
        node1->val = 128;
        node1->parent = node0;
        node1->lchild = nullptr;
        node1->rchild = nullptr;
        node0->rchild = node1;

        /**
         * 下面輸出幾個樹上節點的值，
         * 對於不知道是否存在的女兒，可以先檢查其是否存在，再進行操作處理
         */
        if (root->lchild != nullptr)
            printf("%d\n", root->lchild->val);
        else
            printf("The Node `root` has no children on the left!\n");
        if (root->rchild != nullptr)
            printf("%d\n", root->rchild->val);
        else
            printf("The Node `root` has no children on the right!\n");
        /**
         * 後面的就不檢查直接輸出了。
         * 由於我們設置的node1就是node0的右女兒，
         * 而node0又是root的左女兒，
         * 所以下面三個輸出的應該是同一個值
         */
        printf("%d\n", node1->val);
        printf("%d\n", node0->rchild->val);
        printf("%d\n", root->lchild->rchild->val);
        return 0;
    }

  • 輸出

      7
  The Node `root` has no children on the right!
  128
  128

References

1. 百度百科詞條 二叉樹 ↩