Двоичное дерево поиска: проблема с функцией вставки

Question

Я изучал, как создавать двоичные деревья поиска, и я столкнулся с проблемой при попытке создать свою собственную. Для создания дерева я должен использовать следующую частную структуру. Каждый пример, который я просматривал, использует указатели слева и справа, указывающие на структуру, и я должен использовать левый и правый указатели, указывающие на мой класс шаблонов. Я пытался выяснить, как написать функцию вставки для добавления нового узла в мое дерево, но я все время сталкиваюсь с проблемами из-за настройки этих двух указателей. Кто-нибудь знает, как заставить его работать с этими двумя указателями ниже?

private: 
struct BinaryNode 
{ 
    Comparable element; 
    BinarySearchTree<Comparable> *left; 
    BinarySearchTree<Comparable> *right; 
}; 
BinaryNode *root; 
}; 

Это мой конструктор

BinarySearchTree<Comparable>::BinarySearchTree() { 
BinaryNode *temp; 
temp = new BinaryNode; 

temp->left= NULL; 
temp->right= NULL; 

root = temp; 
} 

Answer 1

Попробуйте следующее:

public: 
    template <typename Comparable> 
    void insert(const Comparable& key) 
    { 
     root = insert(root, key); 
    } 

private: 
    template <typename Comparable> 
    BinaryNode* insert(BinaryNode*& current_node, const Comparable& key) 
    { 
     if (current_node == nullptr) 
     { 
      // Create a leaf node and return it, thus attaching 
      // it to the node we last called the function with 

      return new BinaryNode{key, nullptr, nullptr}; 
     } 

     if (key == current_node->element) 
      // duplicate element, take some action 
     else if (key < current_node->element) 
      current_node->left = insert(current_node->left, key); 
     else 
      current_node->right = insert(current_node->right, key); 

     return current_node; 
    }