使用 C++ 在二叉搜索树中存储值

Question

标准二叉搜索树的代码不包含任何信息，仅包含节点的值。有什么办法可以在节点中包含另一个值，例如年龄？这样节点号将是id，它携带的值将是age。基本上每个节点都会包含一个键值对。感谢您的帮助！

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

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

//to 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;
}

// to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

//function to insert a new node with given key in BST
struct node* initialize(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = initialize(node->left, key);
else if (key > node->key)
node->right = initialize(node->right, key);

/* return the  node pointer */
return node;
}
struct node* insert(node* root, int key)
{
    // Create a new Node containing
    // the new element
    node* newnode = newNode(key);

    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    node* x = root;

    // Pointer y maintains the trailing
    // pointer of x
    node* y = NULL;

    while (x != NULL) {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    // If the root is NULL i.e the tree is empty
    // The new node is the root node
    if (y == NULL) {
        y = newnode;
    }

    // If the new key is less then the leaf node key
    // Assign the new node to be its left child
    else if (key < y->key){
        y->left = newnode;
    }

    // else assign the new node its right child
    else{
        y->right = newnode;
    }
   
    // Returns the pointer where the
    // new node is inserted
    return y;
}

Answer 1

像

一样声明节点

template <typename Key, typename Value>
struct node
{
    Key key;
    Value value;
    struct node *left, *right;
};

请注意，您应该使用 operator new 而不是 malloc。

例如

template <typename Key, typename Value>
struct node<Key, Value>  *newNode( const Key &key, const Value &value )
{
    return new node<Key, Value> { key, value, nullptr, nullptr };
}

也就是说，如果您正在编写 C++ 程序，则使用 C++ 构造。

函数insert可以这样定义

template <typename Key, typename Value>
struct node
{
    Key key;
    Value value;
    struct node *left, *right;
};

template <typename Key, typename Value>
struct node<Key, Value>  * newNode( const Key &key, const Value &value )
{
    return new node<Key, Value> { key, value, nullptr, nullptr };
}


template <typename Key, typename Value>
void insert( node<Key, Value> * &head, const Key &key, const Value &value )
{
    node<Key, Value> **current = &head;

    while ( *current != nullptr )
    {
        if ( key < ( *current )->key ) current = &( *current )->left;
        else current = &( *current )->right;
    }

    *current = newNode( key, value );
}

主要可以写

int main()
{
    node<int, unsigned int> *head = nullptr;

    //…
}

Answer 2

如果这不是大学项目，请不要费心创建自己的二叉搜索树，除非您真的想学习如何做。由于 C++ 以 std::map 和 std::set

的形式为您提供二叉搜索树

std::map<int, std::string> myMap

定义一棵以整数为键的树，存储std::strings.

使用 C++ 在二叉搜索树中存储值

Storing values in binary search tree with C++

c++

tree

nodes

search-tree

binary-search-tree