[資料構造]中位マーキング法の括弧問題8-2


一般的に資料構造の授業では、中尉マーク法の括弧出力は気にしません...
実現しましょう.

ヒント


中尉表記法は3種類あります
  • 3 + 2 * 7
  • 3 + ( 2 * 7 )
  • (3+(2*7)):
  • この式ツリーの式を中位数記号の式として出力します.
    そうなると、同じ結果になります.
    我々は実施前に中位数表記法の出力方式を決定する.
    そして筆者がおすすめする方法は最後の方法です.
    これは、「演算子の数が括弧のペアの数と一致する」ためです.
    これは問題解決のヒントです.
    今、括弧も印刷しましょう.
    上のヒントを理解したら、答えは簡単です!
    ExpressionTree.にある
    void ShowInfixTypeExp(BTreeNode * bt)
    {
        if(bt == NULL)
            return;
        
        if(bt->left != NULL || bt->right != NULL)
            printf(" ( ");
        ShowInfixTypeExp(bt->left);
        ShowNodeData(bt->data);
        ShowInfixTypeExp(bt->right);
        if(bt->left != NULL || bt->right != NULL)
            printf(" ) ");  
    } 
    このコードを追加すればいいです.

    再帰的思考.


    これは木を処理するときに最も重要なようです.
    上のコードもそうです.
    誰もがハーモニーを

  • 「」を生成します.

  • 再びShow~(bt->左)に戻ります

  • bt->左から入って
    root : +
    left : 1
    右:2.
    もしそうであれば、()を作成します.

  • あなたの番組に戻ります~(bt->left)
    root : 1
    左、右:NULL.

  • ルートユーザ1のみが出力されます.
    (||or演算子はleftとrightがNULLの場合に実行されない唯一の演算子であるため).
  • 現在出力されている文字(1)

  • これでleft:1が終了し、root:+が出力されます.
    今right:2の復帰が始まりました.

  • これも5番と同じ出力です.

  • ではroot:+のサブツリーからrightへの再帰はもう終わりました.
    そして左、右ともにNULLを出力する.
  • これまでに出力された文字(1+2)

  • これでroot:intreeのleft:+サブツリーの再帰関数が終了し、root:.が出力されます.

  • 今right:7の復帰は始まりましたか...
    7の左、右=NULLです.
    そのため7万を輸出する.

  • ツリーの左、ルート、右の出力
    終わりました.

  • 同様に、左、右はNULLではありません)が1つ出力されます.

  • 今から!
  • 結論:(1+2)*7).

    出力が成功したことを確認できます.
    最も重要なのは、木の中で、本当の再帰的な思考が重要なようだ.
    やったことを何度も繰り返す場合、復帰を考える可能性があります.
    こんな….どうやって思いついたんだろう.人々は本当に頭がいい......木はこれで終わり...