C语言用指针支持树

关于“C语言用指针支持树”的完整使用攻略，我准备分为以下几个部分进行讲解：

1. 树的定义与基本操作
2. 使用指针实现树节点
3. 树的遍历算法
4. 示例程序

树的定义与基本操作

树是一种非常常见的数据结构，其结构非常清晰，由若干个节点组成，每个节点之间有唯一的父子关系。

一些常见的树操作包括：

• 插入节点：在树中插入一个新节点，将其作为指定节点的子节点。
• 删除节点：从树中删除给定的节点，并将其子节点移动到它的父节点。
• 遍历树：按照一定的顺序遍历树中的每个节点。
• 查找节点：在树中查找给定的节点。
• 计算树的大小：计算树中节点的数量。

使用指针实现树节点

在C语言中，我们可以使用指针来支持树的结构。具体来说，我们可以定义一个节点结构体，其中包含一个数据域和两个指针域，分别指向该节点的左子节点和右子节点。具体定义如下：

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

这里我们定义了一个名为 TreeNode 的结构体，其中包含了一个 int 类型的数据域，以及两个指针域。这种结构表达了树的基本结构。接下来，我们可以通过动态内存分配来创建新节点，并将其链接到树中。

树的遍历算法

在遍历一棵树时，我们可以使用以下三种基本遍历算法：

• 前序遍历：按照根节点、左子树、右子树的顺序遍历树的所有节点。
• 中序遍历：按照左子树、根节点、右子树的顺序遍历树的所有节点。
• 后序遍历：按照左子树、右子树、根节点的顺序遍历树的所有节点。

这三种遍历算法都可以通过递归实现。例如，前序遍历可以用以下方式来实现：

void preorder(struct TreeNode* node) {
    if(node != NULL) {
        printf("%d ", node->data); //打印节点的值
        preorder(node->left); //遍历左子树
        preorder(node->right); //遍历右子树
    }
}

示例程序

下面是一个示例程序，演示如何动态创建一个树，插入节点，并且按照中序遍历的顺序遍历树。

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

void insert(struct TreeNode** node, int data) {
    if(*node == NULL) {
        struct TreeNode* new = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        new->data = data;
        new->left = NULL;
        new->right = NULL;
        *node = new;
    } else if(data < (*node)->data) {
        insert(&(*node)->left, data);
    } else {
        insert(&(*node)->right, data);
    }
}

void inorder(struct TreeNode* node) {
    if(node != NULL) {
        inorder(node->left);
        printf("%d ", node->data);
        inorder(node->right);
    }
}

int main() {
    struct TreeNode* root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 8);
    insert(&root, 1);
    insert(&root, 4);
    insert(&root, 7);
    insert(&root, 9);
    inorder(root); // 中序遍历结果：1 3 4 5 7 8 9
    return 0;
}

在这个示例程序中，我们在 main 函数中创建了一个空树 root，并通过 insert 函数向其中插入了一系列节点。最后，我们通过 inorder 函数按照中序遍历的方式遍历了整个树，并输出了遍历结果。