Binärbaum C++ einfügen und aktualisieren?

Question

Ich möchte ein Binärbaum in C++ machen, die Einfügeoperation führen die eingefügten Werte 4 auf einem Knoten, die

name, type , order, and color 

Die Verwendung werden diese geben 4 als INSERT corn oil 3 yellow ist. Er erstellt einen neuen Knoten mit dem Namen Mais und 3 Kindknoten als Typ, Reihenfolge und Farbe.

Wenn wieder Benutzer gleiche Sache geben, aber andere außer Namen ändern, wie INSERT corn oil 4 red existiert als corn Name existiert dieser Knoten aktualisieren

vorbestellbar und Nachordnungsdurchquerung mit Entfernen und finden Sie einen beliebigen Knoten

Hier ist, wie ich würde, ich möchte ?

 struct TreeNode { 
      string itemname; // The data in this node. 
      TreeNode *left; // Pointer to the left subtree. 
      TreeNode *right; // Pointer to the right subtree. 
     }; 

1- Namens Knoten 2 Werte haben von links nach rechts, wo Platz 4 wird

2- Die Hierarchie der Baumwurzel ist wie nur die Namen, die 2 übrig rechten Knoten haben so Wurzel mit vielen Knoten haben Namen, die nur 2 weitere Knoten, aber nicht mehr Knoten haben, wird zum Kindknoten von Namen hinzugefügt, ist es wirklich ein Baum

Answer 1

Da Sie Binärbaum verwenden, bin ich mir nicht sicher, können Sie Zeichenfolge als Schlüssel für TreeNode (na ja Ich habe immer Intigers benutzt). Also, was ich vorschlagen, dass Sie Struktur wie dieses:

// I am not sure about types, but I assumed them by name 
struct Element { 
    char* name; 
    int type; 
    int order; 
    char* color; 
}; 

struct TreeNode { 
    int key; 
    Element *element; 
    TreeNode *left, *right; 
}; 

Dann würden Sie irgendwie Hash Element::name berechnen einen numerischen Wert zu erhalten, die ein Schlüssel ist. Jetzt würden Sie einfach Baum von der Wurzel nach links oder rechts durchqueren, je nach Schlüssel. Sie würden auf jedem Knoten überprüfen, ob der Schlüssel, den Sie einfügen, derselbe wie einer im aktuellen Knoten ist, und wenn die Antwort ja ist, dann würden Sie Werte in diesem Knoten austauschen, ansonsten den Baum weiter nach links oder rechts durchlaufen. Wenn Sie nach unten gehen, heißt das, dass Sie keinen Knoten mit diesem Schlüssel gefunden haben, also erstellen Sie einen neuen Knoten und hängen ihn als Blatt an.

Sie können diese link aussehen, um Hash zu generieren. Beachten Sie jedoch, dass Sie für eine Zeichenfolge denselben Hash-Wert erhalten können, sodass Sie möglicherweise mehr als ein Element am aktuellen Baumknoten aufbewahren müssen.

UPDATE

Hier ist der Code, Sie aber es mithilfe Zeiger mehr optimieren können. Aber wie in den Kommentaren erwähnt, sollten Sie HashTable oder std::map verwenden, wenn Sie nicht unbedingt verpflichtet sind, den Binärbaum zu verwenden.

std::map<std::string, struct Element*> elements

und zum Abrufen von Element:

Element *e = elements["corn"]

Binary Tree Umsetzung:

#include <iostream> 
#include <vector> 

#define A 54059 /* a prime */ 
#define B 76963 /* another prime */ 
#define C 86969 /* yet another prime */ 
#define FIRSTH 37 /* also prime */ 



struct Element { 
    std::string name; 
    std::string type; 
    int order; 
    std::string color; 
}; 

struct TreeNode { 
    int key; 
    std::vector<Element> values; 
    struct TreeNode *left; 
    struct TreeNode *right; 
}; 

/** 
* see: https://stackoverflow.com/questions/8317508/hash-function-for-a-string 
*/ 
int calculateHash(const char *s) 
{ 
    int h = FIRSTH; 
    while (*s) { 
     h = (h * A)^(s[0] * B); 
     s++; 
    } 
    return h; // or return h % C; 
} 

void printElement(Element element) 
{ 
    std::cout 
      << element.name 
      << " " 
      << element.type 
      << " " 
      << element.order 
      << " " 
      << element.color 
      << std::endl; 
} 

void preOrder(TreeNode* node) 
{ 
    if(node == NULL) 
     return; 

    for(size_t i=0; i<node->values.size(); i++) { 
     printElement(node->values[i]); 
    } 

    preOrder(node->left); 
    preOrder(node->right); 
} 

void insert(TreeNode** root, Element element, int key) 
{ 
    if(*root == NULL) { 
     TreeNode* node = new TreeNode(); 
     node->key = key; 
     node->values.push_back(element); 
     *root = node; 
     return; 
    }; 

    if(key == (*root)->key) { 
     for(size_t i=0; i<(*root)->values.size(); i++) { 
      if((*root)->values[i].name == element.name) { 
       (*root)->values[i].type = element.type; 
       (*root)->values[i].order = element.order; 
       (*root)->values[i].color = element.color; 
       break; 
      } 
     } 
    } 

    else if(key < (*root)->key) { 
     insert(&((*root)->left), element, key); 
    } 

    else { 
     insert(&((*root)->right), element, key); 
    } 
} 

int main() 
{ 
    TreeNode *node = NULL; 
    insert(&node, {"corn1", "oil", 3, "yellow"}, calculateHash("corn1")); 
    insert(&node, {"corn2", "oil", 3, "yellow"}, calculateHash("corn2")); 
    insert(&node, {"corn3", "oil", 3, "yellow"}, calculateHash("corn3")); 

    insert(&node, {"corn2", "aaa", 32, "blue"}, calculateHash("corn2")); 

    preOrder(node); 
    return 0; 
}