6

整数、左と右のポインターを持つバイナリ ツリーが与えられた場合、O(n) 時間と O(1) 余分なメモリ (スタック/キュー/再帰なし) でツリーをトラバースするにはどうすればよいでしょうか?

この男は、現在のパスを整数としてエンコードした O(n) 合計時間ではないソリューションを提供しました (したがって、限られた深さのツリーで機能します)。

私は古典的な解決策を探しています

（ネタバレ）

子の各ノードの親をエンコードしました。

4

5 に答える 5

6

優れたアルゴリズムの本には、このアルゴリズムが含まれています。たとえば、Knuth (TAOCP I.2.3.1 Traversing binary trees, excercise 21) を参照してください。ただし、このアルゴリズムはツリーをその場で変更するため、マルチスレッド環境では細心の注意を払う必要があります。

スレッド ツリーを使用することもできます (Knuth を参照)。

于 2009-04-05T09:47:03.440 に答える
3

主なアイデアは、ポインターが (現在人間に知られているすべての言語で) 0 モードであるという事実に基づいて、1 つの非常に醜いトリッキーなハック (理論的な観点からは、おそらくチート) を持つリスト反転アルゴリズムに似ています。整数として 4。

アイデアは、ツリーを下るパス上のポインターを反転して上を指すことができるということです。問題は、これがリスト反転アルゴリズムから逸脱するところです。バックトラックするとき、左が上か右が上かを知る必要があります。その時点でハックを使用します。

疑似コードは次のとおりです。

current = root->left
next = current
while (current != null) {
  next = current->left
  current->left = static_cast<int>(prev) + 1 // ugly hack.
  current = next
}
status = done
while (current != root or status != done) {
  if (status = done) {
     if (static_cast<u32>(current->left) %4 = 1) {
         next = static_cast<u32>(current->left) -1
         current->left = prev
         status = middle
     }
     else {
         next = current->right
         current->right = prev
         status = done
     }
     prev = current
     current = next
  }
  else if (status == left) {
     if (current->left) {
       prev = current->left
       current->left = static_cast<u32>(next) +1
       next = current
     }
     else
       status = middle
  }
  else if (status == right) {
     if (current->right) {
        prev = current->right;
        current ->right = next;
        next = current
     }
     else
       status = done
  }
  else {// status == middle
     work_on_node(current)
     status = right
  }
}
于 2009-04-07T06:05:51.880 に答える
1

その男のアルゴリズムは興味深いものですが、n 個のノードを持つバイナリ ツリーをトラバースするには O(log n) 個の余分なビットのスペースが必要であることを指摘する必要があります。スペース要件は、バイト単位ではなくビット単位で測定する必要があります。通常、Big Oh 表記法を使用すると、それらは同じものにまとめられますが、このようなケースでは、区別することが重要である理由が指摘されています。

これを確認するには、(32 ビット プラットフォームで) ストレージの単一の整数を使用して、2^32-1 を超えるノードを持つツリーをトラバースする方法を尋ねます。

于 2009-04-06T03:17:28.423 に答える
0

O（1）ストレージを使用して、「最後にアクセスしたノード」ポインターを記憶します。0または不明な値に初期化できます。

ツリーを歩くには、ルートノードから開始します。ノードの両方の子を見てください。「最後にアクセスしたノード」がRIGHTノードと等しい場合は、親ノードに移動します。「最後にアクセスした」がLEFTノードと等しい場合は、右側のノードに進みます。それ以外の場合は、左側のノードに進みます。

木全体を歩き終えるまで繰り返します。唯一の本当の賢さは、次にどこに行くかを決定するために、あなたがどこから来たのかを覚えるために1つの変数を使用することです。これにより、トラバーサルが決定論的になります。

最終的にO（n）ステップを実行します。すべてのミドルノードに3回アクセスし、すべてのリーフに1回アクセスするため、O（N）のままです。ストレージはO（1）です。

于 2009-04-06T12:14:34.420 に答える
0

ここに別の解決策があります

http://sites.google.com/site/debforit/effective-binary-tree-traversal-with-two-pointers

しかし、本当の意味でポインターを持たないJavaのような言語でこれを行う方法があるかどうか疑問に思っていました.

于 2010-09-12T15:41:15.480 に答える