Вставить/найти проблемы в двоичном дереве

Question

UPDATE: Эта проблема возникает только при использовании двоичного дерева для строк. Если я чувствую это с помощью ints, все работает нормально!

---

Несколько месяцев назад я написал реализацию двоичного дерева в C++. Все, казалось, все в порядке (вставка, удаление, обход, поиск ...), и я сдал экзамены :) Но теперь, когда я пишу новый класс на основе этого двоичного древовидного класса, метод find кажется багги, но я могу Не найди причину.

В этом случае проблема: find возвращает указатель на узел, но по какой-то причине я могу получить доступ к его переменным-членам только тогда, когда этот узел является корнем. Я не могу понять, почему. Что-то связанное с путаницами? Или что-то не так в моей функции вставки? Может кто-то помочь мне, потому что я чувствую себя немного потерял :)

Вот мой интерфейс Binary Tree:

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

Наконец , функция, которая проверяет find. Даже если значения совпадают, он возвращает только True, если найденный узел равен m_root. Зачем?

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

Почему?

Другие ссылки: Полный код моей реализации Binary Tree: https://github.com/vgratian/CS-121-Data-Structures/tree/master/graphs программы, где я использую это бинарное дерево: https://github.com/vgratian/rate-ur-prof

Answer 1

проблема заключается в вашей реализации найти:

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

это работает только для типов/классов, для которых реляционные операторы < и > являются (соответствующим образом). Так что это не сработает, например, B - это std::string.

Для сопоставления строк рассмотрите возможность использования Trie.

Answer 2

в функции вставки, вы на самом деле не вставить элемент в дерево. вы создаете новый узел и устанавливаете его родительский указатель на себя. Кроме того, вы не обновили родительские указатели слева и справа на новый узел.

посмотрите в добавленных комментариев:

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