Вставка в двоичное дерево поиска C ++ с помощью рекурсии - PullRequest
Новая
       19

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

0 голосов
/ 16 октября 2008

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

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

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

Ответы [ 3 ]

5 голосов
/ 16 октября 2008

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

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

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

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

Чтобы написать height (), я бы сделал это: 

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));
}
0 голосов
/ 16 октября 2008

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

@ Дуги:
Рассмотрите возможность изменения функции вставки следующим образом: 

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

(непроверенный код)

0 голосов
/ 16 октября 2008

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

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*/
}
...