将值存储在带有C++的二叉搜索树中

Question

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

#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;
};

请注意，您应该使用运算符 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。