14

プレオーダー、インオーダー、ポストオーダーのツリー トラバーサル アルゴリズムをよく理解しています。（参照）。私はいくつかの用途を理解しています: 二分探索木を順番にトラバースするための in-order 、木のクローンを作成するための pre-order です。しかし、私は一生、注文後のトラバーサルが必要な現実世界のタスクを思いつくことはできません。

例を教えてください。そして、事前注文トラバーサルのより良い使い方を教えてください。

編集: 式ツリーと RPN 以外の例を教えてください。それは本当にすべてのポストオーダーが良いのでしょうか?

4

2 に答える 2

17

トポロジカル ソートは、ツリー (または有向非巡回グラフ) のポスト オーダー トラバーサルです。

グラフのノードはタスクを表し、 から までのエッジは のA前に実行する必要があることをB示します。トポロジー ソートは、タスクのすべての依存関係がタスク自体よりも前に現れるように、これらのタスクを順番に並べます。UNIX makeのようなビルド システムは、このアルゴリズムを実装する必要があります。AB

Dario が言及した例 (手動のメモリ管理でツリーのすべてのノードを破棄する) は、この問題の例です。結局、ノードを破棄するタスクは、その子の破棄に依存します。

于 2010-08-21T08:54:04.797 に答える
4

Henk Holterman が指摘したように、手動のメモリ管理を使用してツリーを破棄することは、通常、ポストオーダー トラバーサルです。

擬似コード:

destroy(node) {
  if (node == null) return;

  destroy(node.left)
  destroy(node.right)

  // Post-order freeing of current node
  free(node)
}
于 2010-08-20T16:09:28.423 に答える