如何在C++实现的二叉搜索树节点中存储ID与年龄的键值对

Absolutely—extending your BST nodes to hold a key (as ID) and an additional age field is totally doable. You just need to adjust the node structure and update all functions that create or interact with nodes to handle the new data. Let's modify your code step by step to make this work.

Step 1: Update the Node Structure #

First, add the age field to your node struct so each node holds both an ID (key) and an age:

struct node {
    int key; // This will serve as the ID
    int age; // The new age field we're adding
    struct node *left, *right;
};

Step 2: Modify the newNode Function #

Your original newNode only initializes the key—update it to accept both key and age parameters and set both fields:

// Creates a new BST node with given key (ID) and age
struct node *newNode(int key, int age) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = key;
    temp->age = age; // Initialize the new age field
    temp->left = temp->right = NULL;
    return temp;
}

Step 3: Update Insertion Functions #

Both your recursive (initialize) and iterative (insert) insertion functions need to pass the age parameter to newNode:

Recursive Insert (initialize) #

// Recursively inserts a new node with given key and age into the BST
struct node* initialize(struct node* node, int key, int age) {
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key, age);
    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = initialize(node->left, key, age);
    else if (key > node->key)
        node->right = initialize(node->right, key, age);
    /* Return the unchanged node pointer */
    return node;
}

Iterative Insert (insert) #

struct node* insert(node* root, int key, int age) {
    // Create a new node with the given key and age
    node* newnode = newNode(key, age);
    // Pointer to traverse from root to find insertion point
    node* x = root;
    // Trailing pointer to track parent of x
    node* y = NULL;
    while (x != NULL) {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    // If tree is empty, new node becomes root
    if (y == NULL) {
        y = newnode;
    }
    // Insert as left child if key is smaller than parent's key
    else if (key < y->key){
        y->left = newnode;
    }
    // Insert as right child otherwise
    else{
        y->right = newnode;
    }
    // Return the pointer to the inserted node
    return y;
}

Step 4: Update Traversal to Show Both Fields #

Modify the inorder function to print both the ID (key) and age so you can verify the data is stored correctly:

// Inorder traversal of BST, prints ID and age for each node
void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("ID: %d, Age: %d \n", root->key, root->age);
        inorder(root->right);
    }
}

Example Usage #

Here's how you'd use the updated code to insert nodes with ID and age:

int main() {
    struct node *root = NULL;
    root = initialize(root, 10, 25);
    insert(root, 5, 30);
    insert(root, 15, 22);
    
    // Print all nodes in sorted order (by ID)
    inorder(root);
    return 0;
}

This will output:

ID: 5, Age: 30 
ID: 10, Age: 25 
ID: 15, Age: 22 

The BST still maintains its ordering based on the key (ID) field, while each node now stores the associated age value.

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