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-> 왼쪽 또는 Node-> 오른쪽으로 호출 된 모든 호출 후에 처음 호출 될 때만 루트 일뿐입니다.

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

Answer 2

당신은 당신의 뿌리를 null로 시작해야합니다. 또한, 당신은 *& node를 통과하고 있습니다; *노드 여야합니다. 그렇지 않으면 당신은 주소에 대한 포인터를 전달합니다 (또는 참조,이 맥락에서 어떤 것이 확실하지 않지만 둘 다 옳지 않을 것입니다). 참조가 아니라 노드에 포인터를 전달해야합니다.

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 ()에 대한 호출은 다음과 같습니다.

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

(테스트되지 않은 코드)