C语言二叉搜索树：中位数、均值最接近值查找删除求助

Hey there! Let's work through your BST implementation issues together. You mentioned struggling with median find/delete, displaying the updated BST, and adding functionality to delete the node closest to the mean. Let's break this down step by step, starting with filling in the gaps in your code and fixing common pitfalls.

Your existing code cuts off at the newNode function—let's finish that and add essential helper functions (like insert and inorder traversal) to test your BST:

#include<stdio.h>
#include<stdlib.h>
#include<math.h> // For absolute value checks when finding closest to mean

struct Node {
    int key;
    struct Node* left, *right;
};

// Create a new BST node
struct Node *newNode(int item) {
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Insert a key into the BST
struct Node* insert(struct Node* node, int key) {
    if (node == NULL) return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    return node;
}

// Inorder traversal (verifies BST structure and helps visualize nodes)
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

The median depends on the number of nodes:

• For an odd count: It's the middle node in the inorder traversal
• For an even count: We'll use the left-middle node (you can adjust this to the right-middle if needed)

Step 2.1: Count Total Nodes #

First, we need to know how many nodes are in the BST to find the median position:

// Count total nodes in the BST
int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

Step 2.2: Locate the Median Node #

Use inorder traversal to find the node at the median position:

// Helper to find the median node via inorder traversal
void findMedianNode(struct Node* root, int targetPos, int* currentPos, struct Node** medianNode) {
    if (root == NULL || *medianNode != NULL) return;
    
    findMedianNode(root->left, targetPos, currentPos, medianNode);
    
    (*currentPos)++;
    if (*currentPos == targetPos) {
        *medianNode = root;
        return;
    }
    
    findMedianNode(root->right, targetPos, currentPos, medianNode);
}

// Wrapper to get the median key
int getMedianKey(struct Node* root) {
    int totalNodes = countNodes(root);
    if (totalNodes == 0) return -1; // Empty BST
    
    // Calculate target position (adjust for even counts if needed)
    int targetPos = (totalNodes % 2 == 1) ? (totalNodes + 1)/2 : totalNodes/2;
    int currentPos = 0;
    struct Node* medianNode = NULL;
    
    findMedianNode(root, targetPos, &currentPos, &medianNode);
    return medianNode->key;
}

Step 2.3: Delete the Median Node #

BST deletion has three cases to handle (no children, one child, two children)—this is where many bugs happen:

// Find the smallest node in a subtree (for two-child deletion)
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

// Delete a node with a given key from the BST
struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) return root;
    
    // Traverse to the target node
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        // Case 1: Node has no children or one child
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        
        // Case 2: Node has two children (replace with inorder successor)
        struct Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

Step 2.4: Delete Median & Display Updated BST #

Add a wrapper function to tie this together:

void deleteMedianAndDisplay(struct Node** root) {
    if (*root == NULL) {
        printf("BST is empty!\n");
        return;
    }
    int medianKey = getMedianKey(*root);
    printf("Deleting median node: %d\n", medianKey);
    *root = deleteNode(*root, medianKey);
    
    printf("Updated BST (inorder): ");
    inorder(*root);
    printf("\n");
}

Step 3.1: Calculate Sum & Mean #

First, compute the sum of all node keys to find the mean:

// Calculate sum of all node keys
int calculateSum(struct Node* root) {
    if (root == NULL) return 0;
    return root->key + calculateSum(root->left) + calculateSum(root->right);
}

Step 3.2: Locate the Node Closest to the Mean #

Traverse the BST to find the node with the smallest absolute difference from the mean:

// Helper to find the node closest to the mean
void findClosestToMean(struct Node* root, double mean, int* closestKey, double* minDiff) {
    if (root == NULL) return;
    
    double currentDiff = fabs(root->key - mean);
    // Update if current node is closer, or same distance but smaller key
    if (currentDiff < *minDiff || (currentDiff == *minDiff && root->key < *closestKey)) {
        *minDiff = currentDiff;
        *closestKey = root->key;
    }
    
    findClosestToMean(root->left, mean, closestKey, minDiff);
    findClosestToMean(root->right, mean, closestKey, minDiff);
}

// Wrapper to get the key closest to the mean
int getClosestToMeanKey(struct Node* root) {
    if (root == NULL) return -1;
    int totalNodes = countNodes(root);
    int sum = calculateSum(root);
    double mean = (double)sum / totalNodes;
    printf("Mean of BST nodes: %.2f\n", mean);
    
    int closestKey = root->key;
    double minDiff = fabs(root->key - mean);
    findClosestToMean(root, mean, &closestKey, &minDiff);
    return closestKey;
}

Step 3.3: Delete Closest Node & Display #

Add a wrapper for this functionality too:

void deleteClosestToMeanAndDisplay(struct Node** root) {
    if (*root == NULL) {
        printf("BST is empty!\n");
        return;
    }
    int closestKey = getClosestToMeanKey(*root);
    printf("Deleting node closest to mean: %d\n", closestKey);
    *root = deleteNode(*root, closestKey);
    
    printf("Updated BST (inorder): ");
    inorder(*root);
    printf("\n");
}

int main() {
    struct Node* root = NULL;
    // Insert test nodes
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    
    printf("Original BST (inorder): ");
    inorder(root);
    printf("\n\n");
    
    // Test median deletion
    deleteMedianAndDisplay(&root);
    printf("\n");
    
    // Test closest-to-mean deletion
    deleteClosestToMeanAndDisplay(&root);
    
    return 0;
}

• Incomplete Deletion Logic: Forgetting to handle the two-child deletion case (replacing with the inorder successor) is a frequent bug.
• Integer Division for Mean: Using sum / totalNodes instead of casting to double will truncate the mean, leading to incorrect closest-node calculations.
• Memory Leaks: Not freeing the deleted node in the deleteNode function can cause memory issues over time.
• Median Position Miscalculation: Forgetting to adjust the target position for even node counts can lead to picking the wrong median.

内容的提问来源于stack exchange，提问作者user9408453