0

だから私のコードは以下です。エラーは発生せず、すべてがノードに正常に配置されます。しかし、私のデバッグステートメントに基づいて、何かが挿入されるたびにルートを見つけています。それが正しいかどうかはわかりません。しかし、割り当ての出力ファイルによると、ツリーの高さ、トラバーサルに関しては私の答えが異なり、葉のカウント機能にまだ問題があります。別の話ですが。

デバッグ ステートメントに基づくと、すべてが正しい方向に進んでいるように見えます。しかし、新鮮な目が必要かもしれないと思います。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);
      }
   }
4

3 に答える 3

5

デバッグステートメントの文言を変更する必要があります

本当に読むべきです（ルートノードではありません）

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

node->left または node->right を指定して呼び出すと、最初に呼び出されたときにのみルートになり、中間ノードになります。

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));
}
于 2008-10-16T05:10:58.820 に答える
0

ルートを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*/
}
于 2008-10-16T06:18:20.057 に答える
0

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

(未テストのコード)

于 2008-10-16T06:51:00.537 に答える