バイナリツリーを右にスレッドする

Question

私はこれを理解しようとしています。私が見ているところでは、リストを実際に理解することができます。誰もが最初にリストを通過して実際の先行/後継ノードを見つけることができるので、ノードクラスでそれらのフラグを立てることができます。私は簡単なバイナリ検索ツリーを作成し、リストを通過し、ヌルリンクを先行/後継に再ルーティングできる必要があります。私は多少、以下のような溶液を用いて、いくつかの運を持っていた：

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

Answer 1

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

Node { 
    left 
    right 
} 

を...左と右を使用してこれらの設定のバイナリツリーがあり、ツリーの深度最初の探索から二重リンクリストを作成するように左と右に値を再割り当てしたいと考えています。

あなたが今までに持っていた根本的な問題は、トラバーサル中に渡される "ノードp"（以前の？の略）が現在のツリーのどこから独立している必要があるか常に以前に訪問したノードを含む必要があります。これを行うには、スレッドが実行されるたびに、同じ「前の」変数を参照する必要があります。私はあなたが慣れ親しんでいないなら、1つのC-ismでPython-ish擬似コードを実行しました。 '&'は「への参照」（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でこれを実装しようとしていた場合、あなたが実際に参照を保持するために二重のポインタが必要と思いますが、考え方は同じです - あなたは「最後の訪問ノード」の場所を永続化する必要がありますトラバース全体で