C语言中迭代式删除二叉树根节点的方法及BST删除代码解析

Let's walk through how to implement iterative deletion of a node—including the root—in a Binary Search Tree (BST) using your student node scenario. I'll build on the code snippet you provided and fill in the missing logic for all deletion cases.

First, a quick recap: Iterative BST deletion has three core steps:

1. Locate the target node (your code already starts this with the strcmp checks)
2. Handle one of three possible child scenarios for the target node
3. Update the parent's pointer (or the root if the target was the root) to keep the BST valid

Breaking Down the Three Deletion Cases #

Let's go through each case in detail, since your code only started the leaf node handling:

Case 1: Target Node is a Leaf (No Children) #

This is straightforward. We just need to disconnect the node from its parent (or set the root to NULL if the target was the root) and free the node's memory.

Case 2: Target Node has Exactly One Child #

We bypass the target node by linking its parent directly to its single child. Again, if the target was the root, we update the root pointer to point to that child.

Case 3: Target Node has Two Children #

This is the most complex case. To maintain BST properties, we replace the target node with either:

• The inorder predecessor (the largest node in the left subtree)
• The inorder successor (the smallest node in the right subtree)

We'll use the inorder successor here—we find it, copy its data to the target node, then delete the successor (which will fall into either Case 1 or 2, making it easy to handle).

Complete Iterative Deletion Code #

Here's the full working implementation, built from your initial snippet:

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

// Define your student BST node structure
struct BstStudent {
    char name[50];
    // Add other student data fields here (e.g., student ID, grade)
    struct BstStudent* left;
    struct BstStudent* right;
};

void Bst_DeleteStudent(struct BstStudent** root, char student_name[]) {
    struct BstStudent* current = *root;
    struct BstStudent* parent = NULL;
    int found = 0;

    // Step 1: Find the target node and track its parent
    while (current != NULL) {
        int cmp = strcmp(current->name, student_name);
        if (cmp > 0) {
            parent = current;
            current = current->left;
        } else if (cmp < 0) {
            parent = current;
            current = current->right;
        } else {
            found = 1; // Target node found
            break;
        }
    }

    if (!found) {
        printf("Student '%s' not found in the BST.\n", student_name);
        return;
    }

    // Step 2: Handle each deletion case
    // Case 1: No children (leaf node)
    if (current->left == NULL && current->right == NULL) {
        if (parent == NULL) { // Target is the root
            *root = NULL;
        } else if (parent->left == current) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        free(current);
    }
    // Case 2: Only right child exists
    else if (current->left == NULL) {
        if (parent == NULL) { // Target is root
            *root = current->right;
        } else if (parent->left == current) {
            parent->left = current->right;
        } else {
            parent->right = current->right;
        }
        free(current);
    }
    // Case 2: Only left child exists
    else if (current->right == NULL) {
        if (parent == NULL) { // Target is root
            *root = current->left;
        } else if (parent->left == current) {
            parent->left = current->left;
        } else {
            parent->right = current->left;
        }
        free(current);
    }
    // Case 3: Two children exist
    else {
        // Find inorder successor (smallest node in right subtree)
        struct BstStudent* succ_parent = current;
        struct BstStudent* successor = current->right;
        while (successor->left != NULL) {
            succ_parent = successor;
            successor = successor->left;
        }

        // Copy successor's data to the target node
        strcpy(current->name, successor->name);
        // Copy any other student fields here (e.g., current->id = successor->id)

        // Delete the successor node (it has 0 or 1 child)
        if (succ_parent->left == successor) {
            succ_parent->left = successor->right;
        } else {
            succ_parent->right = successor->right;
        }
        free(successor);
    }
}

Key Implementation Details #

• Root Handling: We use a double pointer (struct BstStudent** root) so we can modify the root pointer directly if the node being deleted is the root.
• Memory Safety: Always free the deleted node to prevent memory leaks.
• BST Property Preservation: Using the inorder successor ensures that after deletion, the BST still maintains its ordering property (left subtree nodes < parent < right subtree nodes).
• String Comparison: strcmp works here because we're comparing null-terminated student names—make sure your name field is always properly terminated.

内容的提问来源于stack exchange，提问作者Minh Nguyen Nhat