-1

二分探索木を扱う表示関数で問題が発生しています。私が抱えている主な問題は、ノードに昇順で番号を付けることができるように、再帰関数でカウント変数を正しくインクリメントすることです。

グローバル変数を数えることはできますか?

関数のコードは次のとおりです。

(p はツリーのルートを指し、count は最初は 1 に設定されています)

void displayAscend(nodePtr p, int count)
   {
      if (p->left != NULL)
         displayAscend(p->left, count);

      cout << count << ". " << p->acctNum << endl;
      count++;

      if (p->right != NULL)
         displayAscend(p->right, count);
   }
4

4 に答える 4

3

参照 int& でカウントを渡します。

void displayAscend(nodePtr p, int& count)
于 2012-04-27T19:13:58.657 に答える
2

変化する

displayAscend(p->left, count);

に

displayAscend(p->left, count+1);

を含む行と同じp->rightです。

于 2012-04-27T19:12:49.763 に答える
2

あなたは次のようなものが欲しいと思います：

size_t displayAscend(nodePtr p, int count)
{
   size_t additional_count = 0;
   if (p->left != NULL)
      additional_count += displayAscend(p->left, count + additional_count);

   cout << count + additional_count << ". " << p->acctNum << endl;
   additional_count++;

   if (p->right != NULL)
      additional_count += displayAscend(p->right, count + additional_count);

   return additional_count;
}

int必要に応じて代わりに使用できますsize_t。

その理由は、各再帰呼び出しがその呼び出し元にカウントを返さなければならないためです。そうしないと、呼び出し元は再帰呼び出しが何回カウントされたかを知ることができません。もちろん、最も外側の呼び出し元は、関心がない場合はカウントを破棄できます。

私の好みの方法ではありませんが、別の答えが観察するように、参照渡しはそれを行う別の方法です。(個人的には、明示的なポインターを使用してその戦略を実装することを好みます。)

countグローバル変数の作成が機能するかどうかを尋ねます。答えは、はい、限られた演習の制限された目的のためには機能しますが、それはひどいプログラミングの実践を表すということです. 結局のところ、それぞれ独自のカウントを持つ複数のツリーがある場合はどうなるでしょうか?

更新: 私のコードの以前のエラーを指摘してくれた @JerryCoffin に感謝します。上記で修正しました。さらに、次の方法でテストしました。

#include <vector>
#include <iostream>
using std::cout;
using std::endl;

struct node {
   node *left;
   node *right;
   int acctNum;
};

typedef node *nodePtr;

size_t displayAscend(nodePtr p, int count)
{
   size_t additional_count = 0;
   if (p->left != NULL)
      additional_count += displayAscend(p->left, count + additional_count);

   cout << count + additional_count << ". " << p->acctNum << endl;
   additional_count++;

   if (p->right != NULL)
      additional_count += displayAscend(p->right, count + additional_count);

   return additional_count;
}

int main() {
   node head;
   node n1;
   node n2;
   node n11;
   node n21;
   node n22;
   head.left  = &n1;
   head.right = &n2;
   n1  .left  = &n11;
   n1  .right = 0;
   n2  .left  = &n21;
   n2  .right = &n22;
   n11 .left  = 0;
   n11 .right = 0;
   n21 .left  = 0;
   n21 .right = 0;
   n22 .left  = 0;
   n22 .right = 0;
   n11 .acctNum = 100;
   n1  .acctNum = 202;
   head.acctNum = 300;
   n21 .acctNum = 400;
   n2  .acctNum = 500;
   n22 .acctNum = 600;
   displayAscend(&head, 0);
}

出力は

0. 100
1. 202
2. 300
3. 400
4. 500
5. 600

だから、それは動作します。

于 2012-04-27T19:16:05.983 に答える
1

カウント変数を参照渡しする必要があります。

void displayAscend(nodePtr p, int & count)
   {
      if (p->left != NULL)
         displayAscend(p->left, count);

      cout << count << ". " << p->acctNum << endl;
      count++;

      if (p->right != NULL)
         displayAscend(p->right, count);
   }
于 2012-04-27T19:17:59.317 に答える