バイナリツリーでの問題の挿入/検索

Question

UPDATE：この問題は、文字列にバイナリツリーを使用する場合にのみ表示されます。私がintでそれを感じるなら、すべてうまくいく！

---

数ヶ月前、私はC++でバイナリツリーの実装を書いていました。すべてが正常に動作するように見えました（挿入、削除、トラバーサル、見つける...）、私は私の試験に合格しました:)しかし、今、私はこのバイナリツリークラスに基づいて新しいクラスを書くと、findメソッドはバグのようです理由を見つけることができません。

findはノードへのポインタを返しますが、何らかの理由でこのノードがルートである場合にのみメンバー変数にアクセスできます。私はなぜそれほど理解できないのですか？ poitersとは何か？または、私の挿入機能に何か問題がありますか？私は失われた:)

をここで少しは私のバイナリツリーインターフェイスで感じるので、誰かが、私を助けることができる：

template <class N> 
class Node { 
public: 
    N data; 
    Node* left; 
    Node* right; 
    Node* parent; 
}; 

template <class B> 
class BinaryTree { 
protected: 
    Node<B>* m_root; 
    unsigned int m_height; // longest path in tree 
    unsigned int m_size; // total number of nodes 

    // methods that support public methods of below 
    void __insert(Node<B>* element, B value); 
    void __inorder(Node<B>* element); 
    void __preorder(Node<B>* element); 
    void __postorder(Node<B>* element); 
    void __remove(Node<B>* element, B value); 
    void __update_parent(Node<B> *element); 
    void __destroy_tree(Node<B>* element); 
    int __get_height(Node<B>* element); 
    Node<B>* __find(Node<B>* element, B value); 
    Node<B>* __find_minimal(Node<B> *element); 

public: 
    BinaryTree(); // Default constructor 
    ~BinaryTree(); // Default deconstructor 
    void insert(B value); 
    void inorder(); 
    void preorder(); 
    void postorder(); 
    void remove(B value); 
    int get_size(); 
    int get_height(); 
    bool is_empty(); 
    bool find(B value); 
    bool check_find(B value); 
}; 

を挿入：

template <class B> 
void BinaryTree<B>::insert(B value) {  // Creates a new node in the tree with value 
    if(m_root == NULL) { 
    m_root = new Node<B>; // creating the root if it's empty 
    m_root->data = value; 
    m_root->left = NULL; 
    m_root->right = NULL; 
    m_root->parent = NULL; 
    } 
    else { 
    Node<B>* element = m_root; 
    __insert(element, value); 
    } 
} 

template <class B> 
void BinaryTree<B>::__insert(Node<B>* element, B value) { 
    if(value < element->data) { 
    if(element->left != NULL) 
     __insert(element->left, value); 
    else { 
     element = element->left; 
     element = new Node<B>; 
     element->data = value; 
     element->left = NULL; 
     element->right = NULL; 
     element->parent = element; 
     m_size++; 
    } 
    } 
    else if(value >= element->data) { 
    if(element->right != NULL) 
     __insert(element->right, value); 
    else { 
     element = element->right; 
     element = new Node<B>; 
     element->data = value; 
     element->left = NULL; 
     element->right = NULL; 
     element->parent = element; 
     m_size++; 
    } 
    } 
} 

検索：最後に

template <class B> 
Node<B>* BinaryTree<B>::__find(Node<B>* element, B value) { 
    if(element != NULL) { 
    if(value == element->data) 
     return element; 
    else if(value < element->data) 
     __find(element->left, value); 
    else if(value > element->data) 
     __find(element->right, value); 
    } 
    else 
    return NULL; 
} 

テストを見つける関数です。値が一致しても、見つかったノードがm_rootの場合はTrueのみを返します。どうして？

template <class B> 
bool BinaryTree<B>::check_find(B value) { 
    Node<B>* node = __find(m_root, value); 
    if(node != NULL && node->data == value) 
    return true; 
    return false; 
} 

なぜですか？

その他のリンク：私のバイナリツリーの実装の 全コード： https://github.com/vgratian/CS-121-Data-Structures/tree/master/graphs 私はこの二分木を使用してプログラム：あなたの挿入機能で https://github.com/vgratian/rate-ur-prof

Answer 1

問題があなたの検索の実装である：

が追加されたコメントで見てみましょう関連する方法で定義されています。したがって、 Bが std::stringであるとうまくいきません。

文字列照合の場合は、Trieを使用することを検討してください。

Answer 2

、あなたが実際にツリーに要素を挿入しないでください。 新しいノードを作成し、それ自身を指すように親ノードを設定します。また、新しいノードへの親左/右ポインタを更新しませんでした。関係演算子が<と>とする型/クラスについて

else if(value < element->data) 
    __find(element->left, value); 
else if(value > element->data) 
    __find(element->right, value); 

これだけ作品：

if(element->left != NULL) 
    __insert(element->left, value); 
else { // meaning element->left == NULL 
    element = element->left; // element = NULL 
    element = new Node<B>; // element = new node 
    element->data = value; 
    element->left = NULL; 
    element->right = NULL; 
    element->parent = element; // element->parent = new node.element parent point to himself