C语言 超详细总结讲解二叉树的概念与使用

1. 什么是二叉树？

二叉树是一种树状数据结构，其中每个节点最多有两个子节点，被称为左子节点和右子节点。具有以下几个特点：

• 每个节点最多有两个子节点；
• 左子节点可以为空，右子节点也可以为空；
• 二叉树的每个节点最多有一个父节点；
• 二叉树通常定义为递归模式定义，即每个节点都可以看做一棵新的二叉树。

2. 二叉树的遍历方式

二叉树的遍历方式分为三种：

• 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树；
• 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树；
• 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的实现

在 C 语言中，我们通常会使用结构体去实现二叉树，结构体包含节点的值，左子节点指针和右子节点指针。示例如下：

typedef struct node{
    int val;            // 节点的值
    struct node* left;  // 左子节点指针
    struct node* right; // 右子节点指针
}node;

node* createNode(int val){  // 创建新节点
    node* newNode = (node*)malloc(sizeof(node));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

4. 二叉树的操作

4.1 插入节点

在二叉树中插入节点通常需要先找到要插入的位置。如果要插入的节点的值小于当前节点的值，那么我们就去找左子树；如果要插入的节点的值大于当前节点的值，那么我们就去找右子树。当找到一个空节点时，就把要插入的节点放在这个空节点上。

void insert(node** root, int val){
    if(*root == NULL){  // 如果根节点为空，直接放置新节点
        *root = createNode(val);
    }else if(val <= (*root)->val){  // 如果要插入的节点的值小于当前节点的值，那么我们就去找左子树
        insert(&((*root)->left), val);
    }else{  // 如果要插入的节点的值大于当前节点的值，那么我们就去找右子树
        insert(&((*root)->right), val);
    }
}

4.2 查找节点

查找节点的方式与插入节点类似，如果要查找的节点的值小于当前节点的值，那么我们就去找左子树；如果要查找的节点的值大于当前节点的值，那么我们就去找右子树。如果找到该节点，就返回该节点的指针；如果找不到该节点，就返回 NULL。

node* search(node* root, int val){
    if(root == NULL || root->val == val){  // 如果根节点为空或根节点的值就是要查找的值，就返回根节点
        return root;
    }else if(val < root->val){  // 如果要查找的节点的值小于当前节点的值，那么我们就去找左子树
        return search(root->left, val);
    }else{  // 如果要查找的节点的值大于当前节点的值，那么我们就去找右子树
        return search(root->right, val);
    }
}

4.3 删除节点

删除节点通常需要分三种情况讨论：

• 要删除的节点是叶子节点，直接删除即可；
• 要删除的节点只有一个子节点，把子节点传给其父节点即可；
• 要删除的节点有两个子节点，需要找到右子树的最小节点并将其传给要删除的节点的位置。

node* delete(node* root, int val){
    if(root == NULL){  // 如果根节点为空，直接返回
        return NULL;
    }else if(val == root->val){  // 如果要删除的节点就是根节点
        if(root->left == NULL){  // 如果左子节点为空，就返回右子节点
            return root->right;
        }else if(root->right == NULL){  // 如果右子节点为空，就返回左子节点
            return root->left;
        }else{  // 找到右子树的最小节点并将其传给要删除的节点的位置
            node* minNode = findMin(root->right);
            root->val = minNode->val;
            root->right = delete(root->right, minNode->val);
        }
    }else if(val < root->val){  // 如果要删除的节点的值小于当前节点的值，那么我们就去找左子树
        root->left = delete(root->left, val);
    }else{  // 如果要删除的节点的值大于当前节点的值，那么我们就去找右子树
        root->right = delete(root->right, val);
    }
    return root;
}

5. 二叉树的示例

5.1 插入和查找节点

int main(){
    // 创建二叉树
    node* root = NULL;
    insert(&root, 10);
    insert(&root, 5);
    insert(&root, 20);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 15);
    insert(&root, 25);

    // 查找节点
    node* n = search(root, 7);
    if(n != NULL){
        printf("Node found: %d\n", n->val);
    }else{
        printf("Node not found.\n");
    }

    // 插入节点
    insert(&root, 12);

    // 查找节点
    n = search(root, 12);
    if(n != NULL){
        printf("Node found: %d\n", n->val);
    }else{
        printf("Node not found.\n");
    }

    return 0;
}

输出：

Node found: 7
Node found: 12

5.2 删除节点

int main(){
    // 创建二叉树
    node* root = NULL;
    insert(&root, 10);
    insert(&root, 5);
    insert(&root, 20);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 15);
    insert(&root, 25);

    // 删除节点
    root = delete(root, 5);

    // 查找节点
    node* n = search(root, 5);
    if(n != NULL){
        printf("Node found: %d\n", n->val);
    }else{
        printf("Node not found.\n");
    }

    return 0;
}

输出：

Node not found.