C语言：树

在C语言中，树（Tree）是一种常见的数据结构，用于表示分层关系或层次结构的数据集合。树在计算机科学中广泛应用，包括但不限于文件系统、解析表达式、数据压缩、决策树等。

1. 基本概念

节点（Node）：树的基本组成单元。每个节点包含数据和指向子节点的指针。
根节点（Root Node）：树的顶部节点，没有父节点。
叶子节点（Leaf Node）：没有子节点的节点。
父节点（Parent Node）：有子节点的节点。
子节点（Child Node）：有父节点的节点。
兄弟节点（Sibling Nodes）：拥有同一父节点的节点。
树的高度（Height）：从根节点到最深的叶子节点的路径中节点的最大数目。
树的深度（Depth）：从根节点到某个节点的路径长度。

2. 树的类型

二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）。
完全二叉树：除了最下层外，每一层都是满的，并且最下层的节点都靠左排列。
满二叉树：所有层都完全填满。
平衡二叉树：任意节点的左右子树的高度差不超过1。
多叉树（N-ary Tree）：每个节点可以有多个子节点。
二叉搜索树（Binary Search Tree, BST）：是一种特殊的二叉树，左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。
AVL树：一种自平衡的二叉搜索树，确保树的左右子树的高度差不超过1。
红黑树：一种自平衡的二叉搜索树，满足特定条件以保证树的高度不超过2log(n)。

3. 树的操作

创建树：分配内存并初始化节点。
插入：将新节点插入到树的适当位置。
删除：从树中删除节点。
遍历：访问树的每个节点，可以是先序、中序、后序、层序遍历等。
搜索：在树中查找特定值的节点。

4. C语言实现

定义
- 在C语言中，树通常通过定义节点结构体来实现。例如，一个简单的二叉树节点可以这样定义：

// 定义树的节点结构
typedef struct TreeNode {
    int data; // 数据域
    struct TreeNode *left;  // 左子节点
    struct TreeNode *right; // 右子节点
} TreeNode;

然后，可以通过递归或非递归的方式来实现树的各种操作。

创建节点
- 动态分配内存为节点赋值：

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

插入节点（以二叉搜索树为例）

TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data); // 根节点为空，创建新节点
    }
    if (data < root->data) {
        root->left = insert(root->left, data); // 插入到左子树
    } else {
        root->right = insert(root->right, data); // 插入到右子树
    }
    return root;
}

遍历树
- 前序遍历（Preorder）
  访问顺序：根 -> 左 -> 右

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);          // 访问根节点
        preorderTraversal(root->left);     // 遍历左子树
        preorderTraversal(root->right);    // 遍历右子树
    }
}

中序遍历（Inorder）
- 访问顺序：左 -> 根 -> 右

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);      // 遍历左子树
        printf("%d ", root->data);         // 访问根节点
        inorderTraversal(root->right);     // 遍历右子树
    }
}

后序遍历（Postorder）
访问顺序：左 -> 右 -> 根

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);    // 遍历左子树
        postorderTraversal(root->right);   // 遍历右子树
        printf("%d ", root->data);         // 访问根节点
    }
}

释放树的内存
- 为了避免内存泄漏，必须递归释放所有节点：

void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);  // 释放左子树
        freeTree(root->right); // 释放右子树
        free(root);            // 释放当前节点
    }
}

5. 示例

以下是一个基于C语言实现的二叉搜索树（Binary Search Tree, BST）的案例。这个例子包含了创建树、插入节点、删除节点、搜索节点和遍历树的基本操作：

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

// 定义树节点结构体
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 创建一个新节点
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入操作
struct TreeNode* insert(struct TreeNode* root, int value) {
    // 如果树为空，新建一个根节点
    if (root == NULL) return createNode(value);

    // 否则，递归找到插入位置
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

// 中序遍历（Inorder Traversal）
void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 搜索节点
struct TreeNode* search(struct TreeNode* root, int key) {
    // 如果树为空或者当前节点就是要找的节点
    if (root == NULL || root->data == key)
       return root;

    // 递归查找
    if (root->data < key)
       return search(root->right, key);

    return search(root->left, key);
}

// 找到最小值的节点
struct TreeNode* minValueNode(struct TreeNode* node) {
    struct TreeNode* current = node;

    // 循环找到最左边的叶子节点
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    // 如果树为空
    if (root == NULL) return root;

    // 否则，递归找到要删除的节点
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // 节点有0个或1个子节点
        if (root->left == NULL) {
            struct TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode *temp = root->left;
            free(root);
            return temp;
        }

        // 节点有两个子节点，获取右子树中的最小节点
        struct TreeNode* temp = minValueNode(root->right);

        // 将该最小节点的数据复制到当前节点
        root->data = temp->data;

        // 删除右子树中的最小节点
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 释放树的内存
void freeTree(struct TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 主函数
int main() {
    struct TreeNode* root = NULL;
	SetConsoleOutputCP(65001);     //设置控制台程序输出的代码页编码为utf-8格式,否则，中文会出现乱码
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("中序遍历结果：\n");
    inorderTraversal(root);
    printf("\n");

    int key = 20;
    struct TreeNode* res = search(root, key);
    if(res != NULL)
        printf("找到值 %d\n", key);
    else
        printf("未找到值 %d\n", key);

    root = deleteNode(root, 20);
    printf("删除20后，中序遍历结果：\n");
    inorderTraversal(root);
    printf("\n");

    // 释放树的内存
    freeTree(root);

    return 0;
}