двоичное дерево C++ вставка и обновление?

Question

Я хочу сделать бинарное дерево в C++, которые выполняют вставки операций вставленных значений 4 на узле, который

name, type , order, and color 

Использование будет ввести эти 4 в INSERT corn oil 3 yellow. Он создает новый узел с именем как кукуруза и 3 дочерних узла как тип, порядок и цвет.

Если снова пользователь вводит то же самое, но изменить любой другой, кроме имени, которое существует как INSERT corn oil 4 red, как corn имя существует это обновит узлу

предпорядком и postorder обход с Вытащите и найти любой узел

Вот как я иду ?

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

1- Имя узла будет иметь 2 значения влево именно там, где будут 4-е место

2- Иерархия дерева, как корень есть только имена, которые имеют 2 оставили правый узел так, корень имеет множество узлов с имена, у которых есть только 2 дополнительных узла, но не больше узла будут добавлены в дочерний узел имен, это действительно дерево

Answer 1

Поскольку вы используете двоичное дерево, я не уверен, что вы можете использовать строку в качестве ключа для TreeNode (хорошо Я всегда использовал интигеры). Так что я предлагаю, что у вас есть структура вроде этого:

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

Тогда вы бы как-то вычислить хэш Element::name, чтобы получить числовое значение, которым является ключом. Теперь вы просто пересечете дерево от корня влево или вправо в зависимости от ключа. Вы должны проверять каждый узел, если введенный вами ключ является таким же, как и в текущем узле, и если ответ да, то вы должны менять значения в этом узле, в противном случае продолжить перемещение дерева влево или вправо. Если вы дойдете до низа, это означает, что вы не нашли узел с этим ключом, поэтому вы создаете новый и прикрепляете его как лист.

Вы можете посмотреть этот link для генерации хэша. Однако имейте в виду, что для некоторой строки вы можете получить одно и то же значение хэша, поэтому вам может потребоваться сохранить более одного элемента в текущем узле дерева.

UPDATE

Вот код, однако вы можете оптимизировать его больше с помощью указателей. Но, как упоминалось в комментариях, если вы не строго обязаны использовать двоичное дерево, вы должны использовать HashTable или std::map.

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

и для извлечения элемента: осуществление

Element *e = elements["corn"]

Binary Tree:

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