ドラゴンブックの第2章の質問

Question

29ページで、「左から右へ読む解析木の葉は、樹木の収量を形成します。樹木の収量は、図2.2では、生成された文字列は9-5 * 2です。この図では、すべての葉が最下段に表示されていますので、必ずしもこのように葉を並べるわけではありません。何故なの？

「すべてのツリーは、aとbが同じ親を持つ2人の子供であり、aがbの左側にあるという考えに基づいて、その葉に自然な左から右の順序を与えますaのすべての子孫はbの子孫の左にあります。どういう意味ですか？それはこれについてコメントしたい他の誰のために、上記ページ番号が最初の版を参照して、すべての書籍

Answer 1

の第二版は、だから、最初だ

P.S。第2版​​では、ページ番号は46であり、参照される図は図2.5である。

EDIT：著者は、葉を下に伸ばしていると言いますが、ツリーのすべての葉をツリー内の同じレベルにあるかどうかにかかわらず、互いに垂直に並べるように移動します。図2.2に示すように、すべての葉がダイアグラムの下部にあり、左から右に垂直に整列されています。この本の後の他の図を見ると、これは行われず、他のノードが葉であるかどうかにかかわらず、同じレベルの他のノードと垂直に並べられた葉が表示されます。この後者の方法は、樹木を描く通常の方法であり、最も効率的です。

あなたの最初の質問については、彼らがそれをしない理由は、部屋を節約することだと思います。図2.4の右側を見ると、作者が葉を下に伸ばしていたのでは、文字をルートとするサブツリーを実際には何よりも余裕を持って右に移動する必要があります必要です。これは最小のケースであり、大きな違いはありませんが、もっと大きな部屋が必要な大きな木（私は見ていませんが、確かに本にあります）を想像することができます。

2番目の質問では、a * b + c * dがあり、その掛け算を兄弟として考えると（操作の順序を有効にするため）、aとbは式の中でcとdの左にあるように、木の中のcとdの左にあるでしょう。基本的には、最初の部分で既に述べたように、つまり、ツリーの葉は、元の構文を正確に再現するために左から右へ読むことができるべきであり、左から右へc * d + a * b、それでも有効かもしれないが、我々が検討している木ではないだろう）。