【数据结构】树与二叉树（十九）：树的存储结构——左儿子右兄弟链接结构（树、森林与二叉树的转化）

Qomolangma

发布于 2024-07-30 10:27:29

3840

文章被收录于专栏：深度学习深度学习

5.1 树的基本概念

5.1.1 树的定义

一棵树是结点的有限集合T：
- 若T非空，则：
  - 有一个特别标出的结点，称作该树的根，记为root(T)；
  - 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0)，其中T1, T2, …, Tm又都是树，称作root(T)的子树。
- T 空时为空树，记作root(T)=NULL。

5.1.2 森林的定义

一个森林是0棵或多棵不相交（非空）树的集合，通常是一个有序的集合。换句话说，森林由多个树组成，这些树之间没有交集，且可以按照一定的次序排列。在森林中，每棵树都是独立的，具有根节点和子树，树与树之间没有直接的连接关系。森林是树的扩展概念，它是由多个树组成的集合。在计算机科学中，森林也被广泛应用于数据结构和算法设计中，特别是在图论和网络分析等领域。

5.1.3 树的术语

父亲（parent）、儿子（child）、兄弟（sibling）、后裔（descendant）、祖先（ancestor）
度（degree）、叶子节点（leaf node）、分支节点（internal node）
结点的层数
路径、路径长度、结点的深度、树的深度

参照前文：【数据结构】树与二叉树（一）：树（森林）的基本概念：父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

5.2 二叉树

5.3 树

5.3.1 树的存储结构

1. 理论基础

Father链接结构:
- 在这种结构中，每个节点除了存储数据外，还包含一个指向其父节点的指针。
- 这种结构使得查找父节点很容易，但对于查找子节点则较为困难，因为需要遍历整个树。
- 在二叉树中，每个节点最多有一个父节点，但在一般的树中，节点可以有多个父节点。
儿子链表链接结构:
- 在这种结构中，每个节点包含一个指向其第一个子节点的指针，以及一个指向其下一个兄弟节点的指针。
- 这种结构使得查找子节点很容易，但查找父节点较为困难，可能需要遍历兄弟节点链表直到找到相应的父节点。
左儿子右兄弟链接结构:
- 也称为孩子兄弟表示法，每个节点包含一个指向其第一个子节点的指针，以及一个指向其下一个兄弟节点的指针。
- 在这种结构中，树的每一层被表示为一个单链表，子节点通过左链连接，兄弟节点通过右链连接。
- 这种结构既方便查找父节点，又方便查找子节点和兄弟节点，被广泛用于一般的树的表示。

选择合适的树的存储结构通常取决于具体应用的需求。 Father链接结构适合于查找父节点的操作频繁，而儿子链表链接结构和左儿子右兄弟链接结构适用于频繁查找子节点的情况。

2. 典型实例

Father链接结构:
- A节点：父指针为null（A为根节点）
- B节点：父指针指向A
- C节点：父指针指向A
- D节点：父指针指向A
- E节点：父指针指向C
- F节点：父指针指向C
儿子链表链接结构:
- A节点：子节点链表为B、C、D
- B节点：子节点链表为null
- C节点：子节点链表为E、F
- D节点：子节点链表为null
- E节点：子节点链表为null
- F节点：子节点链表为null
左儿子右兄弟链接结构:
- A节点：左儿子为B，右兄弟为null
- B节点：左儿子为null，右兄弟为C
- C节点：左儿子为E，右兄弟为D
- D节点：左儿子为null，右兄弟为null
- E节点：左儿子为null，右兄弟为F
- F节点：左儿子为null，右兄弟为null

3. Father链接结构

4. 儿子链表链接结构

【数据结构】树与二叉树（十八）：树的存储结构——Father链接结构、儿子链表链接结构

5. 左儿子右兄弟链接结构

左儿子右兄弟链接结构通过使用每个节点的三个域（FirstChild、Data、NextBrother）来构建一棵树，同时使得树具有二叉树的性质。具体来说，每个节点包含以下信息：

FirstChild： 存放指向该节点的大儿子（最左边的子节点）的指针。这个指针使得我们可以迅速找到一个节点的第一个子节点。
Data： 存放节点的数据。
NextBrother： 存放指向该节点的大兄弟（同一层中右边的兄弟节点）的指针。这个指针使得我们可以在同一层中迅速找到节点的下一个兄弟节点。

通过这样的结构，整棵树可以用左儿子右兄弟链接结构表示成一棵二叉树。这种表示方式有时候被用于一些特殊的树结构，例如二叉树、二叉树的森林等。这种结构的优点之一是它更紧凑地表示树，而不需要额外的指针来表示兄弟关系。

   A
  /|\
 B C D
  / \
 E   F

A
|
B -- C -- D
     |
     E -- F

即：

a. 定义树节点

typedef struct TreeNode {
    char data;
    struct TreeNode* firstChild;
    struct TreeNode* nextBrother;
} TreeNode;

b. 创建树节点

TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->firstChild = NULL;
        newNode->nextBrother = NULL;
    }
    return newNode;
}

c. 使用左儿子右兄弟链接结构将树转化为二叉树

TreeNode* convertToBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }

    // 处理第一个子节点
    TreeNode* binaryFirstChild = convertToBinaryTree(root->firstChild);

    // 处理下一个兄弟节点
    TreeNode* binaryNextBrother = convertToBinaryTree(root->nextBrother);

    // 构建二叉树
    root->firstChild = binaryFirstChild;
    root->nextBrother = binaryNextBrother;

    return root;
}

【数据结构】树与二叉树（十二）：二叉树的递归创建（算法CBT）

d. 前序遍历二叉树

【数据结构】树与二叉树（七）：二叉树的遍历（先序、中序、后序及其C语言实现）

void printBinaryTree(TreeNode* root) {
    if (root != NULL) {
        printf("%c ", root->data);
        printBinaryTree(root->firstChild);
        printBinaryTree(root->nextBrother);
    }
}

e. 释放树

void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->firstChild);
        freeTree(root->nextBrother);
        free(root);
    }
}

f. 主函数

int main() {
    // 构建左儿子右兄弟链接结构的树
    TreeNode* A = createNode('A');
    TreeNode* B = createNode('B');
    TreeNode* C = createNode('C');
    TreeNode* D = createNode('D');
    TreeNode* E = createNode('E');
    TreeNode* F = createNode('F');

    A->firstChild = B;
    B->nextBrother = C;
    C->nextBrother = D;
    C->firstChild = E;
    E->nextBrother = F;

    // 转化为二叉树
    TreeNode* binaryRoot = convertToBinaryTree(A);

    // 打印二叉树
    printf("Binary Tree (Preorder): ");
    printBinaryTree(binaryRoot);
    printf("\n");

    // 释放树节点
    freeTree(binaryRoot);

    return 0;
}

6. 代码整合

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

// 定义树节点
typedef struct TreeNode {
    char data;
    struct TreeNode* firstChild;
    struct TreeNode* nextBrother;
} TreeNode;

// 创建树节点
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->firstChild = NULL;
        newNode->nextBrother = NULL;
    }
    return newNode;
}

// 将左儿子右兄弟链接结构转化为二叉树
TreeNode* convertToBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }

    // 处理第一个子节点
    TreeNode* binaryFirstChild = convertToBinaryTree(root->firstChild);

    // 处理下一个兄弟节点
    TreeNode* binaryNextBrother = convertToBinaryTree(root->nextBrother);

    // 构建二叉树
    root->firstChild = binaryFirstChild;
    root->nextBrother = binaryNextBrother;

    return root;
}

// 打印二叉树（前序遍历）
void printBinaryTree(TreeNode* root) {
    if (root != NULL) {
        printf("%c ", root->data);
        printBinaryTree(root->firstChild);
        printBinaryTree(root->nextBrother);
    }
}

// 释放树节点及其子树
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->firstChild);
        freeTree(root->nextBrother);
        free(root);
    }
}

int main() {
    // 构建左儿子右兄弟链接结构的树
    TreeNode* A = createNode('A');
    TreeNode* B = createNode('B');
    TreeNode* C = createNode('C');
    TreeNode* D = createNode('D');
    TreeNode* E = createNode('E');
    TreeNode* F = createNode('F');

    A->firstChild = B;
    B->nextBrother = C;
    C->nextBrother = D;
    C->firstChild = E;
    E->nextBrother = F;

    // 转化为二叉树
    TreeNode* binaryRoot = convertToBinaryTree(A);

    // 打印二叉树
    printf("Binary Tree (Preorder): ");
    printBinaryTree(binaryRoot);
    printf("\n");

    // 释放树节点
    freeTree(binaryRoot);

    return 0;
}

7. 森林与二叉树之间的自然对应

从森林到二叉树的映射：
- 对于每一棵树，选择其中的一颗作为二叉树的根，将其余的树作为这个根节点的右子树。这样，每个节点的左子树对应该节点在原树中的第一个子节点，而右子树对应该节点在原树中的兄弟节点。
从二叉树到森林的映射：
- 对于二叉树中的每个节点，将其左子树作为原树中的第一个子节点，将其右子树作为原树中的兄弟节点。这样，每个节点的左子树对应该节点在原树中的第一个子节点，而右子树对应该节点在原树中的兄弟节点。
由上述转换，可以看到，任何一个森林都对应一棵二叉树，逆转这个过程，任何一棵二叉树对应一个唯一的森林。称这个变换为森林与二叉树之间的自然对应。