プログラミングライフでは、常に木の構造に遭遇します。過去数日間で、ツリー構造を操作する必要があるため、独自の操作方法とプロセスを記録します。このような木があると仮定します(それがバイナリツリーであるかどうかは関係ありません、原則は同じです)
1。深さの優先度
英語の略語はDFS、つまり深さの最初の検索です。
深度検索は、開発クローラーの初期段階でより一般的に使用される方法です。その目的は、検索された構造(つまり、ハイパーリンクを含まないHTMLファイル)の葉のノードに到達することです。 HTMLファイルでは、ハイパーリンクが選択されている場合、リンクされたHTMLファイルは深さfirst検索を実行します。つまり、残りのハイパーリンク結果を検索する前に、別のチェーンを完全に検索する必要があります。深さの優先順位検索は、HTMLファイルのハイパーリンクに続いて、さらに深くなることができなくなり、特定のHTMLファイルに戻り、HTMLファイルで他のハイパーリンクを選択し続けます。他のハイパーリンクが利用できない場合、検索は終了しました。このプロセスは、さらに深くなることができなくなるまで、すべての可能なブランチパスに深く入り込むことであり、各ノードには1回しかアクセスできません。上記の例では、深さ第一トラバーサルの結果は次のとおりです。a、b、d、e、i、c、f、g、H。(子ノードの左側が最初に残っていると仮定)。
深さの優先順位は、各ノードを通過するために使用され、ヒープのようなデータ構造が必要です。スタックの特性は、最初に移動してから終了することです。トラバーサルプロセス全体が次のとおりです。
最初に、ノードAをヒープに押し込み、スタック(a)。
ノードAをポップアップし、Aの子ノードCとBを同時にヒープに押し込みます。この時点で、Bはヒープの上部、スタック(B、C)です。
ノードBをポップアップし、Bの子ノードEとDをヒープに押し込みます。この時点で、dはヒープの上部、スタック(d、e、c)にあります。
ポップアップノードD、子ノードは押されておらず、eはヒープの上部にあるスタック(e、c)です。
ノードeをポップアップし、eの子ノードiをスタックに押します(i、c)。
...順番にダウンし、最終的なトラバーサルが完了します。 Javaコードはほぼ次のとおりです。
public void depthfirst(){stack <map <map <string、object >> nodestack = new stack <map <string、object >>(); map <string、object> node = new hashmap <string、object>(); nodestack.add(node); while(!nodestack.isempty()){node = nodestack.pop(); system.out.println(node); //ノードの子ノードを取得します。バイナリツリーの場合、それは左の子ノードとノードリストの右子ノードを取得することです<Map <String、Object >> Children = getChildren(node); if(Children!= null &&!children.isempty()){for(map childer:children){nodestack.push(child);}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}2。幅の優先順位
英語の略語はBFSであり、これは幅広い最初の検索を意味します。プロセステストによると、ノードの各層が順番にアクセスされ、1つのレイヤーにアクセスした後、各ノードは1回のみアクセスできます。上記の例では、幅最初のトラバーサルの結果は次のとおりです。A、B、C、D、E、F、G、H、I(ノードの各層が左から右にアクセスされると仮定)。
幅の優先度は、各ノードを通過するために使用され、キューのようなデータ構造が必要です。キューの特性は最初の最初の、最初のものであり、実際には、両端のキューを使用することもできます。違いは、ノードを挿入して、両端のキューの最初の位置でポップアップできることです。トラバーサルプロセス全体が次のとおりです。
最初にノードをキューに挿入します。キュー(a);
ノードAをポップアップし、キューにチャイルドノードbとcを挿入します。この時点で、Bはキューの先頭にあり、Cはキュー、キュー(b、c)の最後にあります。
ノードBをポップアップし、Child Nodes DとEを同時にキューに挿入します。この時点で、Cはキューの先頭にあり、Eはキューの終わりにあります、キュー(C、D、E)。
ノードCをポップアップし、Cの子ノードF、G、Hをキューに挿入します。この時点で、dはキューの先頭にあり、hはキュー、キュー(d、e、f、g、h)の最後にあります。
ポップアップノードd、dには子ノードがありません。この時点では、eはキューの頭にあり、hはキュー、キュー(e、f、g、h)の尾にあります。
...順番にダウンし、最終的なトラバーサルが完了します。 Javaコードはほぼ次のとおりです。
public void breadfirst(){deque 要約します
上記は、この記事のすべてのコンテンツであり、深さと幅広いJava実装コードの例に関するものであり、すべての人に役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました!