バイナリツリーC++の挿入と更新？

Question

私が挿入された値は、使用がINSERT corn oil 3 yellowとしてこれら4を入力します

name, type , order, and color 

であるノード上で4ある、挿入操作を実行するのC++でのバイナリツリーを作りたいです。これは、型、順序、色としてトウモロコシと3つの子ノードの名前を持つ新しいノードを作成します。

ユーザーが同じものを入力しますが INSERT corn oil 4 redcornとして名前のように存在している名前以外の任意の他の変更を再度した場合、これは削除してノード

行きがけと後順トラバーサルを更新し、任意のノード

を見つける存在ここでどのように向かっています ？ 2つの値を有する

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

1-名ノードが4が所定の位置する場所左右

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のハッシュを計算します：だから私はお勧めすることは、このような構造を持っているということです。今度は、キーに応じてルートから左または右にツリーをたどるだけです。挿入しているキーが現在のノードのものと同じであるかどうかをチェックし、答えがyesの場合はそのノードの値を入れ替えます。そうでなければ、ツリーを左右に移動し続けます。一番下に来たら、そのキーを持つノードを見つけられていないということです。新しいノードを作成し、それをリーフとして接続します。

このlinkを見ると、ハッシュが生成されます。ただし、一部の文字列では同じハッシュ値を得ることができるので、現在のツリーノードに複数の要素を保持する必要があります。

UPDATEここ

は、しかし、あなたは、ポインタを使用して、よりそれを最適化することができ、コードです。しかし、コメントに記載されているように、バイナリツリーの使用に厳密に縛られていない場合は、HashTableまたはstd::mapを使用する必要があります。

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

と要素取得のために：

Element *e = elements["corn"]

バイナリツリーの実装：

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