二叉树札记 I 基础构造

Author: sandyzikun

二叉树的概念等基础知识大部分已在离散数学中学过，在此不再重复或赘述。

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. 百度百科词条 二叉树 ↩