最後のリーフからルートへのツリービューノードを反復するアルゴリズム

Question

最後のリーフからルーツへのWinForms TreeViewコントロールを逆に反復する最適なアルゴリズムは何ですか？ C＃

Answer 1

バイナリツリーの場合、逆インオーダートラバーサルを探しています。これを実行するには、インオーダートラバーサル中にノードをリンクリスト（右のリンクノードを介して）にプッシュできます。次に、リンクされたリストを逆方向にそれを後方に読み取ります。

1. バイナリ検索ツリーを、インオーダートラバーサルO（n）を使用して二重リンクリストに変換します。
2. 2重リンクリストを逆方向にトラバースします。そのために2つのポインタを使用できます。

次に、あなたがBT（二分木）を持っている場合は、rootに葉からツリーを走査するための最良のツリーウォークはポストになる楽しさを持っており、それを最適化:)

Answer 2

をすることができます注文木 - 歩いてください。これは左→右→ルートの順にノードを訪問します。これを逆にするには、right-> left-> rootを使います。

擬似コード：

BottomUpTraversal(x) 
    BottomUpTraversal(x.left) 
    BottomUpTraversal(x.right) 
    print(x.key) 

Answer 3

コードは、以下の各ノードを訪問すると、それが葉になるまで、深さ優先、完全に横切ります。次に、スタックを巻き戻すと、各ノードにDoSomethingWithNodeが呼び出されます。 depthパラメータは、ノードが逆の順序で返されることを示します。これはあなたの最初の最も深いリーフノードを与えるのではなく、ただのリーフノードであることを確認しますしないことを

ReverseTraverse(MyTreeView.Nodes, 1); 

注：

void ReverseTraverse(TreeNodeCollection nodes, int depth) 
{ 
    if (nodes == null) return; 
    foreach (TreeNode child in nodes) 
    { 
     ReverseTraverse(child.Nodes, depth+1); 
     DoSomethingWithNode(child, depth); 
    } 
} 

はMyTreeViewがTreeViewインスタンスであると仮定すると、それを呼び出すにはその親ノードの前に出力します。あなたのツリーは次のようになります場合：

Node 1 
    Node 1.1 
    Node 1.2 
    Node 1.2.1 
Node 2 
    Node 2.1 
    Node 2.1.1 
     Node 2.1.1.1 
    Node 2.1.2 

出力順は次のようになります。

Node 1.1 
Node 1.2.1 
Node 1.2 
Node 1 
Node 2.1.1.1 
Node 2.1.1 
Node 2.1.2 
Node 2.1 
Node 2 

あなたは（すなわちノード2.1.1.1は、第一の出力になります）最初の最も深いノードをしたい場合は、あなたがしたいですフル・トラバーサル（順方向では最も簡単なもの）を作成し、対応する深さのノードのリストを作成する必要があります。次に、リストを深さ（降順）でソートし、順番に出力します。