Вставка двоичного дерева C++ с помощью рекурсии

Question

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

Основываясь на заявлениях отладки, похоже, что все идет правильно там, где они должны. Но я полагаю, что мне могут понадобиться свежие глаза. Я не вижу, как мои обходы могут измениться вообще, потому что это действительно только вопрос, где я обрабатываю узел, который должен воздействовать на Inorder, preorder и postorder.

template <class T> 
void BT<T>::insert(const T& item) 
{ 
    Node<T>* newNode; 
    newNode = new Node<T>(item); 
    insert(root, newNode); 
} 


template <class T> 
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode) 
{ 
    if (root == NULL) 
     { 
      cout << "Root Found" << newNode->data << endl; 
      root = newNode; 
     } 
    else 
     { 
      if (newNode->data < root->data) 
       { 
       insert(root->left, newNode); 
       cout << "Inserting Left" << newNode-> data << endl; 
       } 
      else 
       { 
       insert(root->right, newNode); 
       cout << "Inserting Right" << newNode->data << endl; 
       } 
     } 
} 

Моя функция высоты следующая на всякий случай моя вставка на самом деле хорошо.

template <class T> 
int BT<T>::height() const 
{ 
    return height(root); 
} 


    template <class T> 
    int BT<T>::height(Node<T>* root) const 
    { 
    if (root == NULL) 
     return 0; 
    else 
     { 
     if (height(root->right) > height(root->left)) 
     return 1 + height(root-> right); 
     return 1 + height(root->left); 
     } 
    } 

Answer 1

Вы должны изменить формулировку отладочные

Действительно следует читать (не Корневой узел)

cout << "Leaf Node Found" << newNode->data << endl; 

Это только корень, когда он сначала вызывается после того, что любой вызов с node-> left или node-> right делает его промежуточным узлом.

Чтобы написать высоту() Я бы сделать это:

template <class T> 
int BT<T>::height(Node<T>* root) const 
{ 
    if (root == NULL) {return 0;} 

    return 1 + max(height(root->left),height(root->right)); 
} 

Answer 2

Вы должны начать с корня init'd к нулю. Кроме того, вы проходите * & узел в; он должен быть * узлом. Кроме того, вы передаете указатель на адрес (или ссылку, я не уверен, что в этом контексте, но оба не будут правильными). Вы должны передать указатель на узел, а не ссылку.

template <class T> 
void BT<T>::BT() 
{ root = 0;} 

template <class T> 
void BT<T>::insert(const T& item) 
{ 
    Node<T>* newNode; 
    newNode = new Node<T>(item); 
    insert(root, newNode); 
} 

template <class T> 
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode) 
{ 
/*stuff*/ 
} 

Answer 3

@Vlion:
Он должен быть указателем на левом/правом/корневые указатели (т.е. двойного указателя), поэтому отправил код правильный, хотя и несколько неясно.

@Doug:
следует изменить функцию вставки таким образом:

template <class T> 
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode) 
{ 
    if (*root == NULL) 
     { 
      cout << "Root Found" << newNode->data << endl; 
      *root = newNode; 
     } 

Это проясняет свое намерение, что вы будете меняющимся указатель, передаваемый в качестве первого параметра (или, точнее, указатель, адрес которого будет передается как первый параметр.) Это поможет избежать путаницы, такой как тот, который только что произошел.

Призывы к этой вставки(), например:

insert(&root, newNode); 

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

---

Что касается проверки правильности дерева, почему бы не вытащить его и не увидеть сами?Что-то вдоль линий:

template class<T> 
void printTree(struct Node<T>* node, int level=0) 
{ 
    if (!node) { 
     for (int i=0; i<level; ++i) 
      cout << " "; 
     cout << "NULL" << endl; 

     return; 
    } 

    printTree(node->left, level+1); 

    for (int i=0; i<level; ++i) 
     cout << " "; 
    cout << node->data << endl; 

    printTree(node->right, level+1); 
} 

(непроверенного кода)