C语言数据结构二叉树简单应用

C语言数据结构二叉树简单应用攻略

1. 什么是二叉树？

二叉树（Binary Tree）是一种树形结构，它的每个节点最多包含两个子节点，它是非线性数据结构，可以用来表示许多问题，例如家族关系、计算机文件系统等等。

2. 二叉树的基本操作

二叉树的基本操作包括插入、删除、查找等等，本攻略主要讲解插入和查找的实现。

插入操作的代码如下：

// 二叉树的插入操作
void insert(Node **root, int val) {
    if (*root == NULL) {
        // 树为空，新建节点作为根节点
        *root = (Node *)malloc(sizeof(Node));
        (*root)->val = val;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else {
        // 树非空，将新节点插入到合适的位置
        if (val <= (*root)->val) {
            insert(&((*root)->left), val);
        } else {
            insert(&((*root)->right), val);
        }
    }
}

查找操作的代码如下：

// 二叉树的查找操作
bool search(Node *root, int val) {
    if (root == NULL) {
        // 树为空，未找到目标值
        return false;
    } else if (root->val == val) {
        // 找到目标值
        return true;
    } else if (val < root->val) {
        // 目标值在左子树中
        return search(root->left, val);
    } else {
        // 目标值在右子树中
        return search(root->right, val);
    }
}

3. 二叉树的应用举例

3.1 实例一：二叉查找树

二叉查找树（Binary Search Tree）是一种特殊的二叉树，满足以下条件：

1. 左子树上所有节点的值均小于它的根节点的值；
2. 右子树上所有节点的值均大于它的根节点的值；
3. 左右子树也分别为二叉查找树。

二叉查找树常用于实现关联数组（Associative Array），即能够对键进行查找和插入操作的数据结构。

下面是二叉查找树的插入和查找操作的实现代码：

// 二叉查找树的插入操作
void bst_insert(Node **root, int val) {
    if (*root == NULL) {
        // 树为空，新建节点作为根节点
        *root = (Node *)malloc(sizeof(Node));
        (*root)->val = val;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else {
        // 树非空，将新节点插入到合适的位置
        if (val <= (*root)->val) {
            bst_insert(&((*root)->left), val);
        } else {
            bst_insert(&((*root)->right), val);
        }
    }
}

// 二叉查找树的查找操作
bool bst_search(Node *root, int val) {
    if (root == NULL) {
        // 树为空，未找到目标值
        return false;
    } else if (root->val == val) {
        // 找到目标值
        return true;
    } else if (val < root->val) {
        // 目标值在左子树中
        return bst_search(root->left, val);
    } else {
        // 目标值在右子树中
        return bst_search(root->right, val);
    }
}

3.2 实例二：求二叉树的高度

二叉树的高度是指从根节点到最深叶子节点的最长路径长度。

下面是求二叉树高度的递归实现代码：

// 求二叉树的高度
int height(Node *root) {
    if (root == NULL) {
        // 空树高度为0
        return 0;
    } else {
        // 左子树和右子树中高度更大的一棵加1就是整棵树的高度
        return 1 + max(height(root->left), height(root->right));
    }
}

4. 总结

本攻略主要讲解了二叉树的基本概念、插入和查找操作的实现以及二叉查找树和求二叉树高度的应用举例。二叉树是一种非常重要的数据结构，在计算机科学中有着广泛的应用，例如搜索、排序、存储等等。对于C语言的程序员来说，掌握二叉树的基本操作和应用是一种不可或缺的技能。