当前位置： 首页 > article >正文

C语言：树

article 2024/11/26 12:23:06

在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;
}
  • 这个例子展示了如何创建一个二叉搜索树、插入节点、搜索特定值的节点、删除节点以及遍历树。它还包括了如何在程序结束时释放树的内存以避免内存泄漏。
  • 运行:
    在这里插入图片描述

6. 总结

  • 树是一种重要的数据结构，支持递归操作，常用于表示层次化数据。
  • 在 C 语言中实现树通常需要动态分配内存，使用递归操作处理节点。
  • 避免内存泄漏是树实现中的关键点，需要显式释放节点内存。

http://www.kler.cn/a/409926.html

相关文章：

  • leetcode hot100【LeetCode 238.除自身以外数组的乘积】java实现
  • unity中给刚体施加力的方法介绍
  • 网络原理（一）：应用层自定义协议的信息组织格式 初始 HTTP
  • 微信小程序与公众号关联（同一主体），获取unionId并关联公众号openid
  • 【GPT】睡觉时，大脑在做什么
  • 数据可视化复习2-绘制折线图+条形图（叠加条形图，并列条形图，水平条形图）+ 饼状图 + 直方图
  • tableau练习-制作30个图表
  • elementui el-input修改字体样式
  • Excel把其中一张工作表导出成一个新的文件
  • 1-golang_org_x_crypto_bcrypt测试 --go开源库测试
  • 论文笔记 SliceGPT: Compress Large Language Models By Deleting Rows And Columns
  • 【Android】Android Studio打包APK、精简APK大小与规范处理详解
  • 牛客周赛69第一题：JAVA
  • 红队笔记--W1R3S、JARBAS、SickOS、Prime打靶练习记录
  • 18. 冒泡排序小游戏
  • 人工智能之数学基础：向量的基本知识
  • 企业办公自动化：Spring Boot OA管理系统开发与实践
  • Docker 容器化开发 应用
  • 环境变量简介
  • yolov11的目标检测理论、tensorrt实现推理
  • VScode clangd插件安装
  • ModuleNotFoundError: No module named ‘_ssl‘ centos中的Python报错
  • MaxKB构建本地大语言模型问答系统打造属于你的智能问答应用
  • JavaScript引入和变量
  • Vue 3 异步组件教程
  • 【Docker系列】批量删除特定前缀的镜像 Tag