深入探究C语言中的二叉树

什么是二叉树？

二叉树是一种树形数据结构，它由一个根节点和零个或者多个子树，每个子树也是一棵二叉树。二叉树的特点是每个节点最多只有两个子节点，分别称为该节点的左子节点和右子节点。二叉树在计算机科学领域有着广泛的应用。

二叉树的常用操作

1. 插入节点

在二叉树中插入一个节点有两种情况：如果该节点的值比当前节点的值小，则将该节点插入当前节点的左子树中；反之则将该节点插入当前节点的右子树中。

void insert_node(BinaryTreeNode **root, int value) {
    if (*root == NULL) {
        *root = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
        (*root)->value = value;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else {
        if (value < (*root)->value) {
            insert_node(&((*root)->left), value);
        } else {
            insert_node(&((*root)->right), value);
        }
    }
}

2. 删除节点

在二叉树中删除节点也有两种情况：如果待删除节点没有子节点，则可以直接删除；如果待删除节点有一个子节点，则将该子节点替换成待删除节点的位置；如果待删除节点有两个子节点，则分三种情况考虑：把待删除节点的左子树挂在待删除节点的后继节点（即待删除节点右子树的最左叶子节点）的左子树上，然后把待删除节点的右子树挂在待删除节点的后继节点的右子树上；把待删除节点的左子树挂在待删除节点的前驱节点（即待删除节点左子树的最右叶子节点）的左子树上，然后把待删除节点的右子树挂在待删除节点的前驱节点的右子树上；用待删除节点的后继节点（即待删除节点右子树的最左叶子节点）来代替待删除节点。

void delete_node(BinaryTreeNode **root, int value) {
    if (*root == NULL) {
        return;
    }
    if (value < (*root)->value) {
        delete_node(&((*root)->left), value);
    } else if (value > (*root)->value) {
        delete_node(&((*root)->right), value);
    } else {
        if ((*root)->left == NULL && (*root)->right == NULL) {
            free(*root);
            (*root) = NULL;
        } else if ((*root)->left == NULL) {
            BinaryTreeNode *temp = *root;
            (*root) = (*root)->right;
            free(temp);
        } else if ((*root)->right == NULL) {
            BinaryTreeNode *temp = *root;
            (*root) = (*root)->left;
            free(temp);
        } else {
            BinaryTreeNode *temp = find_min_node((*root)->right);
            (*root)->value = temp->value;
            delete_node(&((*root)->right), temp->value);
        }
    }
}

3. 查找节点

在二叉树中查找一个节点的值，也有两种情况：如果当前节点的值等于待查节点的值，则返回该节点；如果当前节点的值比待查节点的值小，则递归查找左子树；如果当前节点的值比待查节点的值大，则递归查找右子树。

BinaryTreeNode *find_node(BinaryTreeNode *root, int value) {
    if (root == NULL) {
        return NULL;
    } else if (root->value == value) {
        return root;
    } else if (root->value > value) {
        return find_node(root->left, value);
    } else {
        return find_node(root->right, value);
    }
}

示例展示

示例1：构建一棵二叉树

BinaryTreeNode *root = NULL;

insert_node(&root, 5);
insert_node(&root, 3);
insert_node(&root, 7);
insert_node(&root, 1);
insert_node(&root, 9);

这里我们构建了一棵二叉树，节点的值分别是5、3、7、1和9。

示例2：查找二叉树节点

BinaryTreeNode *result = find_node(root, 7);
if (result != NULL) {
    printf("The value of the node is %d\n", result->value);
} else {
    printf("The node not found\n");
}

这里我们查找二叉树中的一个节点，节点的值为7。如果查找成功，则返回该节点；否则返回NULL。