数据结构之二叉树

发布于:2025-05-20 ⋅ 阅读:(22) ⋅ 点赞:(0)

目录

1 简介

2 二叉树的基本概念

3 代码实现

4 代码解析

4.1 节点结构体

4.2 插入节点

4.3 中序遍历

4.4 先序遍历

4.5 后序遍历

4.6 释放二叉树

5 核心操作分析

6 总结


1 简介

在数据结构中,二叉树(Binary Tree)是一种结构非常灵活且应用广泛的非线性结构,广泛用于排序、检索、表达式树、图像处理等领域。本文将使用 C 语言实现一个简单的二叉搜索树(BST),完成其插入、中序遍历、前序遍历、后序遍历以及树的释放等基本操作,为后续掌握平衡树、红黑树等高级树结构打下基础。

2 二叉树的基本概念

二叉树:每个节点最多有两个子节点,分别称为左子节点和右子节点。

二叉搜索树(BST):左子树中所有节点的值都小于根节点,右子树中所有节点的值都大于根节点。

遍历方式:

        中序遍历:左 -> 根 -> 右(常用于排序)

        前序遍历:根 -> 左 -> 右

        后序遍历:左 -> 右 -> 根

3 代码实现

// node.c
// 二叉树的基本操作

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

typedef struct node
{
    int val;
    struct node *left;
    struct node *right;
} Node;

Node *insert(Node *root, int val);
void pre_order(Node *root);
void in_order(Node *root);
void post_order(Node *root);
void free_tree(Node *root);
void delete_tree(Node *root);


int main(int argc, char const *argv[])
{
    Node *root = NULL;

    root = insert(root, 42);
    root = insert(root, 9);
    root = insert(root, 72);
    root = insert(root, 32);
    root = insert(root, 17);

    in_order(root);
    printf("\n");

    free_tree(root);

    in_order(root); // 释放后,root指向的内存已经被释放,不能再访问
    return 0;
}

// 删除树
void delete_tree(Node *root)
{
    if (root == NULL) return;
    delete_tree(root->left);
    delete_tree(root->right);
    free(root);
}

// 释放树
void free_tree(Node *root)
{
    delete_tree(root);
}

// 插入节点
Node *insert(Node *root, int val)
{
    if (root == NULL)
    {
        root = malloc(sizeof(Node));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }

    if (val < root->val)
    {
        // 小于当前节点值,插入左子树
        root->left = insert(root->left, val);
    }
    if (val > root->val)
    {
        // 大于当前节点值,插入右子树
        root->right = insert(root->right, val);
    }
    return root;
}

// 中序遍历
void in_order(Node *root)
{
    if (root == NULL) return;
    in_order(root->left);           // 先中序打印左子树
    printf("%d, ", root->val);        // 打印根
    in_order(root->right);          // 再中序打印右子树
}

// 先序遍历
void pre_order(Node *root)
{
    if (root == NULL) return;
    printf("%d, ", root->val);
    pre_order(root->left);
    pre_order(root->right);
}

// 后序遍历
void post_order(Node *root)
{
    if (root == NULL) return;
    post_order(root->left);
    post_order(root->right);
    printf("%d, ", root->val);
}

4 代码解析

4.1 节点结构体

typedef struct node
{
    int val;
    struct node *left;
    struct node *right;
} Node;

定义了二叉树节点结构,包含整数值 val,指向左子节点和右子节点的指针 leftright,构成了树的基本元素。

4.2 插入节点

Node *insert(Node *root, int val)
{
    if (root == NULL)
    {
        root = malloc(sizeof(Node));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }

    if (val < root->val)
    {
        root->left = insert(root->left, val);
    }
    if (val > root->val)
    {
        root->right = insert(root->right, val);
    }
    return root;
}

该函数用于向二叉搜索树插入新节点。如果当前树为空,创建新节点作为根节点。若插入值小于当前节点,递归插入左子树。若插入值大于当前节点,递归插入右子树。返回更新后的树根指针。

4.3 中序遍历

void in_order(Node *root)
{
    if (root == NULL) return;
    in_order(root->left);
    printf("%d, ", root->val);
    in_order(root->right);
}

中序遍历顺序为:左子树 -> 根节点 -> 右子树。
这使得输出的节点值是升序排列,适用于二叉搜索树的排序输出。

4.4 先序遍历

void pre_order(Node *root)
{
    if (root == NULL) return;
    printf("%d, ", root->val);
    pre_order(root->left);
    pre_order(root->right);
}

先序遍历顺序为:根节点 -> 左子树 -> 右子树。
常用于复制树结构或先访问根节点的场景。

4.5 后序遍历

void post_order(Node *root)
{
    if (root == NULL) return;
    post_order(root->left);
    post_order(root->right);
    printf("%d, ", root->val);
}

后序遍历顺序为:左子树 -> 右子树 -> 根节点。
适合用于释放树资源或后序处理子树。

4.6 释放二叉树

void delete_tree(Node *root)
{
    if (root == NULL) return;
    delete_tree(root->left);
    delete_tree(root->right);
    free(root);
}

void free_tree(Node *root)
{
    delete_tree(root);
}

通过递归后序遍历,先释放左右子树,最后释放根节点,实现安全释放整个树所占内存。

此时的错误说明二叉树的空间已经被释放。

5 核心操作分析

6 总结

本文演示了二叉搜索树的基本实现,包括节点插入和三种常用遍历方式,以及如何释放树内存。代码结构简洁,适合入门学习树形结构操作。理解这些基础操作,为后续实现更复杂的数据结构和算法打下坚实基础。

源码地址:0411/tree.c · jkh111/Niuer_C - 码云 - 开源中国