私はで構築されたバイナリツリーを横断しようとしていますキーボードからの入力データ。データがバイナリツリーに正常に挿入されました。 switch文があります。「case 2」は、再帰を使用してInorder、Preorder、およびPostorderトラバーサルアルゴリズムでバイナリツリーをトラバース(および印刷)する必要があります。ただし、「case 2」が呼び出されると、Inorderトラバーサルに関して印刷される最初のデータのみが画面に印刷されます。また、コンパイル操作を停止する必要がある場所で何度も(無限に)印刷されます。誰かがこれで私を助けてくれたら、私はもっと幸せです。
(RootPtrは、グローバルに定義されたバイナリツリーのトップレベル0-ノードです。また、GetNodeは、基本的にTreePtrポインター型の初期化関数(mallocを使用)です。)
あらかじめありがとうございます。
これは構造体の定義です。
typedef struct treeItem
{
int data;
struct treeItem *left;
struct treeItem *right;
}Tree , *TreePtr;
これら3つはそれぞれ呼び出される走査関数です。
void inorder (TreePtr TemPtr)
{
while(TemPtr != NULL)
{
inorder((*TemPtr).left);
printf(" %d ", (*TemPtr).data);
inorder((*TemPtr).right);
}
printf("n");
}
void preorder (TreePtr TemPtr)
{
while(TemPtr != NULL)
{
printf(" %d ", (*TemPtr).data);
preorder((*TemPtr).left);
preorder((*TemPtr).right);
}
printf("n");
}
void postorder (TreePtr TemPtr)
{
while(TemPtr != NULL)
{
postorder((*TemPtr).left);
postorder((*TemPtr).right);
printf(" %d", (*TemPtr).data);
}
printf("n");
}
これは、switchステートメントの関連する「ケース」です。
case 2:
TreePtr LocPtr;
GetNode(&LocPtr);
LocPtr = RootPtr;
printf("n");
printf("Inorder traversal:");
inorder(LocPtr);
printf("Preorder traversal:");
preorder(LocPtr);
printf("Postorder traversal:");
postorder(LocPtr);
printf("n");
break;
回答:
回答№1は0トラバーサル関数内にwhileループがあってはなりません。再帰性はすべてのノードですでに実行されます。
void inorder (TreePtr TemPtr)
{
if (TemPtr != NULL) {
inorder((*TemPtr).left);
printf(" %d ", (*TemPtr).data);
inorder((*TemPtr).right);
}
printf("n");
}
あなたがそれについて考えるなら、あなたの TemPtr
パラメータは「t」に変更されていません NULL
ループで反復するとき。そのため、無限ループに陥ります。
ツリートラバーサルの説明:
あなたのメインでは、 case 2
、 あなたが呼ぶ inorder
ツリーのルートをパラメーターとして使用します。次に、ツリーを走査する必要があります。
inorder(LocPtr);
順序走査は次のとおりです。
左の子に移動...現在のノードにアクセス...右の子に移動
再帰関数/メソッドには、基本ケースと再帰呼び出しの2つのことが必要です。
ここで、ベースケースは if (TemPtr != NULL)
。この条件がfalseの場合、リーフに到達したことがわかります。もし TemPtr
確かに葉であるため、「エラーをスローする可能性のある」その子までは進みません。
しかし、もし TemPtr
ない NULL
、これは現在有効なノードにいることを意味します。したがって、(前述のように)順序走査の定義に従う必要があります。
左の子供を訪問します。
inorder((*TemPtr).left); // equivalent to inorder(TemPtr->left);
現在のノードにアクセスします。
printf(" %d ", (*TemPtr).data); // equivalent to printf (" %d ", TemPtr->data);
そして、私たちは正しい子を訪問します:
inorder((*TemPtr).right); // equivalent to inorder(TemPtr->right);
いつ inorder
終了、の呼び出し元 inorder
それがあったところに続きます。このプロセスは inorder(LocPtr)
終了すると、この時点でメインに戻り、ツリー全体が順番どおりに走査されます。
これを視覚化する最も簡単な方法は、紙にコールを描くことです。関数は互いにスタックします(main
下部にあります)、終了したらスタックから削除されます。