4

1つの章を読むためにK＆Rに戻ってきましたが、以前に省略していた例に気づきました。この章では、バイナリツリーデータ型のトピックについて説明します。ノードに新しいエントリを保存することは理解していますが、印刷機能を使用すると混乱します。なぜ左側の印刷が最初に呼ばれるのですか？

printf関数の最初のコマンドで、その後に左と右が続く場合、それは機能しますか？

そうでない場合-なぜそれでは？

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}
4

3 に答える 3

9

最初に左側を下降し、次にノード自体を出力し、次に右側を下降することで、この操作はツリーの順序どおりにトラバーサルされます。printfあなたが提案するように、左降下の前に移動した場合、それはトラバーサルを事前注文します。そして、最初に両方の降下を行った場合、それはポストオーダーになります. 3 つの可能性はすべて、すべてのノードを訪問しますが、3 つの異なる順序でアクセスします。

単純な木を考えてみましょう

  *
 / \
a   +
   / \
  b   c

このツリーを事前にトラバースすると、

* a + b c

順番に、

a * b + c

ポストオーダー、

a b c + *

これらの可能性のどれが必要かは、何をしているかによって異なります。

于 2012-09-17T19:54:17.927 に答える
1

もちろん、それは「うまくいく」でしょう。出力の順序が異なるだけです。両方の子ノードを印刷した後にノードを印刷することもできます。(そして、2 つだけでなく、複数の子を持つツリーがあると想像してください。)

本当の問題は、ツリー ノードの値が何らかの特別な規則に従うかどうか、したがって、特定のトラバーサル順序が特に意味があるかどうかです。たとえば、二分探索木の場合、左から右への順序で値がソート順に出力されます。

于 2012-09-17T19:51:05.670 に答える
0

プレオーダー、インオーダー、ポストオーダーなど、さまざまな方法でバイナリ ツリーをたどることができます。

printf は、まったく異なる手順 (ノード データの計算) である可能性があります。一部の問題では、ツリー上を異なる方法で歩く必要があります。たとえば、バイナリ ツリーのバランスを取る場合は、両方の子ツリーにアクセスした後でバランス係数を計算します。

したがって、printf は、さまざまな種類の問題に対処するための他の種類の手順/関数のプレース ホルダーと考えることができます。

于 2012-09-17T19:55:40.850 に答える