任何一个树都可以通过 孩子兄弟表示法 转化为一个二叉树。所以，孩子兄弟表示法 也称为 二叉树链表存储。

树的存储实现有：

  1. 孩子兄弟表示法（最常用，也称 二叉树链表存储）
  2. 双亲表示法
  3. 孩子表示法
  4. 孩子双亲表示法

树的存储实现

孩子兄弟表示法

1
2
3
4
5
6
7
// 左孩子 右兄弟
typedef struct TreeNode
{
    char data;  // 结点中的数据
    struct TreeNode* first_child; // 第一个孩子结点
    struct TreeNode* next_sibling; // 指向下一个兄弟结点
} TreeNode;

为了方便创建结点，需要有创建结点的函数，输入结点的数据，输出结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>

TreeNode* createNode(char data)
{
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode -> data = data;
    newNode -> first_child = NULL;
    newNode -> next_sibling = NULL;

    return newNode;
}

创建自己的树结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    /*
        A
       / \
      B   C
     / \
    D   E
    */
    TreeNode* root = createNode('A');
    root -> first_child = createNode('B');  // 创建子结点 B
    root -> first_child -> next_sibling = createNode('C');  // 创建 B 的兄弟结点 C
    root -> first_child -> first_child = createNode('D');  // 创建 B 的子结点 D
    root -> first_child -> first_child -> next_sibling = createNode('E'); // 创建 D 的兄弟结点 E

    return 0；
}

孩子兄弟表示法，采用的是链式存储各个结点的子结点和兄弟结点。

.png

对于下图所示的树的示意图

.png

经过孩子兄弟表示法之后，变为二叉树

.png

二叉树的遍历

前序遍历 preorder traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void printf(TreeNode *node, int Depth)
{
    for (int i = 0; i <= Depth; i++)
    {
        printf("\t");
    }
    printf("%c", node->data);
    printf("\n");
}

// 以 node 为根节点，向下遍历子树
void ListDir(TreeNode *node, int Depth)
{
    if (node)
    {
        printf(node, Depth);
        ListDir(node->first_child, Depth + 1);
        ListDir(node->next_sibling, Depth);
    }
}