通过递归插入C++二进制搜索树

Question

所以我的代码如下.我没有收到任何错误,它将节点中的所有内容都放好了.但基于我的调试语句每次插入任何内容时它都会找到根.我不确定这是不对的.但根据作业的输出文件,我的答案是不同的,当涉及树的高度,遍历,我只是平坦我仍然有我的叶计数功能的麻烦.另一个故事.

基于调试语句,看起来一切都在他们应该的位置.但我想我可能需要新鲜的眼睛.我不知道我的遍历是如何改变的,因为它实际上只是我处理节点应该影响顺序,预订和后序的问题.

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