[C语言日寄]树结构：从定义到C语言实现

什么是树？

在计算机科学中，树是一种非常重要的非线性数据结构。与线性结构（如数组、链表）不同，树以分层的方式组织数据，这种结构更接近现实世界中许多问题的本质。

任何树都由一个根结点和若干棵子树组成，每棵子树本身也是一棵树。当有多棵（大于0棵）互不相交的树时，我们称之为森林。

树的基本术语

结点关系

• 父结点：除了根结点外，每个结点有且仅有一个父结点
• 子结点：一个结点可以有零个或多个子结点
• 兄弟结点：具有相同父结点的结点互称兄弟结点
• 祖先结点：从根到该结点所经分支上的所有结点
• 堂兄弟结点：父结点在同一层的结点互称堂兄弟结点

层次与度

• 结点的层次：从根开始定义，根为第一层，依次类推
• 结点的度：一个结点拥有的子树数量
• 叶结点：度为0的结点（也称为终端结点）
• 分支结点：度不为0的结点（也称为非终端结点）
• 树的度：树中所有结点的度的最大值

重要性质

一个含有N个结点的树有N-1条边，这是树结构的一个重要特征。

树的C语言实现：左孩子右兄弟表示法

在C语言中，我们可以使用左孩子右兄弟表示法来高效地表示树结构。这种表示法的核心思想是：每个结点只包含两个指针，一个指向它的第一个子结点，另一个指向它的下一个兄弟结点。

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

// 树结点结构定义
typedef struct TreeNode {
    int data;               // 结点数据
    struct TreeNode* firstChild;  // 指向第一个子结点
    struct TreeNode* nextSibling; // 指向下一个兄弟结点
} TreeNode;

// 创建新结点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;
    return newNode;
}

// 添加子结点
void addChild(TreeNode* parent, TreeNode* child) {
    if (parent->firstChild == NULL) {
        parent->firstChild = child;
    } else {
        TreeNode* temp = parent->firstChild;
        while (temp->nextSibling != NULL) {
            temp = temp->nextSibling;
        }
        temp->nextSibling = child;
    }
}

// 前序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);      // 访问根结点
    preOrderTraversal(root->firstChild); // 遍历子树
    preOrderTraversal(root->nextSibling); // 遍历兄弟结点
}

// 计算树的高度
int treeHeight(TreeNode* root) {
    if (root == NULL) return 0;
    
    int maxHeight = 0;
    TreeNode* child = root->firstChild;
    
    while (child != NULL) {
        int height = treeHeight(child);
        if (height > maxHeight) {
            maxHeight = height;
        }
        child = child->nextSibling;
    }
    
    return maxHeight + 1;
}

// 释放树的内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    
    freeTree(root->firstChild);
    freeTree(root->nextSibling);
    free(root);
}

int main() {
    // 创建树结构示例
    TreeNode* root = createNode(1);
    
    TreeNode* node2 = createNode(2);
    TreeNode* node3 = createNode(3);
    TreeNode* node4 = createNode(4);
    TreeNode* node5 = createNode(5);
    
    // 构建树结构：
    //      1
    //     /|\
    //    2 3 4
    //      |
    //      5
    
    addChild(root, node2);
    addChild(root, node3);
    addChild(root, node4);
    addChild(node3, node5);
    
    printf("前序遍历结果: ");
    preOrderTraversal(root);
    printf("\n");
    
    printf("树的高度: %d\n", treeHeight(root));
    
    freeTree(root);
    return 0;
}

树的应用

普通的树在数据结构中直接应用不多（二叉树更为常见）：

1. 文件系统：计算机中的目录结构就是典型的树形结构
2. 组织结构图：公司或机构的层级关系可以用树表示
3. 家谱系统：家族关系天然形成树结构
4. 决策树：人工智能和机器学习中的分类模型

总结

树结构是计算机科学中基础且重要的概念，掌握了树的基本原理和实现方法，将为学习更复杂的数据结构（如二叉树、AVL树、B树等）打下坚实基础。左孩子右兄弟表示法以其简洁性和高效性，成为了表示一般树结构的优选方案。