0

私はこれを理解しようとすると大変な時間を過ごしています。どこを見ても、リストを非再帰的にトラバースする方法（実際に理解している部分）についての説明に出くわしているだけのようです。誰かが最初にリストを調べて実際の先行/後続ノードを見つけてノードクラスでそれらにフラグを立てることができる方法を正確に理解できますか？単純なバイナリ検索ツリーを作成し、リストを調べて、ヌルリンクを先行/後続に再ルーティングできるようにする必要があります。私は次のような解決策で運が良かった：

thread(node n, node p) {
     if (n.left !=null)
        thread (n.left, n);
     if (n.right !=null) {
        thread (n.right, p);
     }
     n.right = p;
}
4

1 に答える 1

1

あなたの説明から、私はあなたが次のような構造を持つノードを持っていると仮定します：

Node {
  left
  right
}

...そして、これらのバイナリツリーが左右を使用して設定されており、値を左右に再割り当てして、深さ優先探索から二重リンクリストを作成するようにします。木。

これまでに得たものの根本的な（しゃれを意図していない）問題は、トラバーサル中に渡される「ノードp」（前の略語？）は、現在のツリーのどこにあるかとは無関係である必要があるということです。以前にアクセスしたノードを含める必要があります。そのためには、スレッドを実行するたびに、同じ「前の」変数を参照する必要があります。1つのC-ismを使用してPython風の擬似コードを作成しました。慣れていない場合は、「＆」は「参照」（またはC＃では「ref」）を意味し、「*」は「逆参照してくれ」を意味します。それが指しているオブジェクト」。

Node lastVisited
thread(root, &lastVisisted)

function thread(node, lastVisitedRef)
  if (node.left)
    thread(node.left, lastVisitedRef)
  if (node.right)
    thread(node.right, lastVisitedRef)

  // visit this node, reassigning left and right
  if (*lastVisitedRef)
    node.right = *lastVisitedRef
    (*lastVisitedRef).left = node
  // update reference lastVisited
  lastVisitedRef = &node

これをCで実装する場合、参照を保持するために実際にはダブルポインターが必要ですが、考え方は同じです。トラバーサル全体で「最後にアクセスしたノード」の場所を保持する必要があります。

于 2009-07-31T04:36:04.950 に答える