この記事では、Javaにバイナリツリーを実装する深度最初のトラバーサルおよび幅最初のトラバーサルアルゴリズムについて説明します。次のように、参照のために共有してください。
1。分析
バイナリツリーの深さ第一トラバーサルの非回復力の一般的な慣行は、スタックを採用することであり、幅広い視聴の非回復力の一般的な慣行は、キューを採用することです。
深さfirstトラバーサル：可能な各ブランチパスは、それ以上深くすることができなくなるまで侵入でき、各ノードには1回しかアクセスできません。バイナリツリーの深さ第一トラバーサルは非常に特別であり、予約注文のトラバーサル、中間トラバーサル、およびその後のトラバーサルに細分化できることに注意する必要があります。特定の説明は次のとおりです。
一次トラバーサル：任意のサブツリーの場合、まずルートにアクセスし、次にその左サブツリーを横断し、最後に右サブツリーを横断します。
ミドルオーダートラバーサル：任意のサブツリーの場合、最初にその左サブツリーを横断し、次にルートにアクセスし、最後にその右サブツリーを通過します。
ポストオーバートラバーサル：任意のサブツリーの場合、最初に左サブツリーを横断し、次に右サブツリーを横断し、最後にルートにアクセスします。
幅次のトラバーサル：階層とも呼ばれ、各レイヤーに上から下にアクセスします。各レイヤーで、左から右（または右から左）にアクセスします。 1つのレイヤーにアクセスした後、アクセスできるノードがなくなるまで次のレイヤーを入力します。
2。例を挙げてください
以下の図に示されているバイナリソーティングツリーには、予約注文トラバーサル（再帰的、非再帰的）、順序のトラバーサル（再帰的、非再帰的）、ポストオーダートラバーサル（再帰的、非再帰的）、および幅広い最初のトラバーサルの使用が必要です。
①参照コード
パッケージbinarytreetraversetest; Import java.util.linkedList; Import java.util.queue;/** *深さ優先順位トラバーサルと幅の優先順位トラバーサル * @authorファンタジー * @version 1.0 2016/10/05-2016/10/07 * binarysorttree <integer> tree = new binarysorttree <integer>（）; tree.insertnode（35）; tree.insertnode（20）; tree.insertnode（15）; tree.insertnode（16）; tree.insertnode（29）; tree.insertnode（28）; tree.insertnode（30）; tree.insertnode（40）; tree.insertnode（50）; tree.insertnode（45）; tree.insertnode（55）; System.out.print（ "事前注文トラバーサル（再帰）："）; tree.PreOrderTraverse（tree.getRoot（））; System.out.println（）; System.out.print（ "順序トラバーサル（再帰）："）; tree.inordertraverse（tree.getRoot（））; System.out.println（）; System.out.println（）; System.out.print（ "順番トラバーサル（再帰）："）; tree.postordertraverse（tree.getRoot（））; System.out.println（）; system.out.print（ "前処理トラバーサル（非再帰）："）; tree.PreOrderTraversENORECURSION（tree.getRoot（））; System.out.println（）; System.out.print（ "順序トラバーサル（非再帰）："）; tree.inordertraversenecursion（tree.getRoot（））; System.out.println（）; System.out.println（）; system.out.print（ "順番トラバーサル（非再帰）："）; tree.postordertraversenecursion（tree.getRoot（））; System.out.println（）; System.out.print（ "Bredthpriority Traversal："）; tree.breadthfirsttraverse（tree.getRoot（））; }}/*** node*/class node <e拡張<e >> {e value; node <e>左; node <e>右; node（e value）{this.value = value;左= null;右= null; }}/** *先例のシーケンスを使用して、バイナリソートツリー（バイナリ検索ツリーとも呼ばれます）を構築します */class binarysorttree <e extends carpleable <e >> {private node <e> root; binarysorttree（）{root = null; } public void insertNode（e値）{if（root == null）{root = new node <e>（value）;戻る; } node <e> currentNode = root; while（true）{if（value.comPareto（currentNode.Value）> 0）{if（currentNode.right == null）{currentNode.right = new node <e>（value）;壊す; } currentNode = currentNode.right; } else {if（currentNode.Left == null）{currentNode.Left = new node <e>（value）;壊す; } currentNode = currentNode.Left; }}} public node <e> getRoot（）{return root; } / ** *バイナリツリーの事前注文トラバーサル（再帰） * @param node * / public void preordertraverse（node <e> node）{system.out.print（node.value + ""）; if（node.left！= null）preordertraverse（node.left）; if（node.right！= null）preordertraverse（node.right）; } / ** *バイナリツリーの順序トラバーサル（再帰） * @param node * / public void inorder traverse（node <e> node）{if（node.left！= null）inordertraverse（node.left）; System.out.print（node.value + ""）; if（node.right！= null）inorderTraverse（node.right）; } / ** *バイナリツリーのポストオーバートラバーサル（再帰） * @param node * / public void postordertraverse（node <e> node）{if（node.left！= null）postordertraverse（node.left）; if（node.right！= null）postorderTraverse（node.right）; System.out.print（node.value + ""）; } / ** *バイナリツリーの事前注文トラバーサル（非再帰） * @param root * / public void preodertraversenorecursion（node <e> root）{linkedlist <node <e >> stack = new linkedlist <node <e >>（）; node <e> currentNode = null; stack.push（root）; while（！stack.isempty（））{currentNode = stack.pop（）; System.out.print（currentNode.Value + ""）; if（currentNode.right！= null）stack.push（currentNode.right）; if（currentnode.left！= null）stack.push（currentNode.Left）; }} / ** *バイナリツリーの注文のトラバーサル（非再帰） * @param root * / public void inordertraversenorecursion（node <e> root）{linkedlist <node <e >> stack = new linkedlist <node <e >>（）; node <e> currentNode = root; while（currentNode！= null ||！stack.isempty（））{//バイナリソーティングツリーの左端の葉のノード（currentNodeはnull）までループ（currentNode！= null）{stack.push（currentNode）; currentNode = currentNode.Left; } currentNode = stack.pop（）; System.out.print（currentNode.Value + ""）; currentNode = currentNode.right; }} / ** *バイナリツリーのポストオーダートラバーサル（非再帰） * @param root * / public void postordertraversenorecursion（node <e> root）{linkedlist <node <e >> stack = new linkedlist <node <e >>（）; node <e> currentNode = root; node <e> rightnode = null; while（currentNode！= null ||！stack.isempty（））{//バイナリソーティングツリーの左端にある葉のノード（currentNodeはnull）の葉のノードがwhile（currentNode！= null）{stack.push（currentnode）; currentNode = currentNode.Left; } currentNode = stack.pop（）; //現在のノードには右ノードまたは前のノード（出力されたノード）は現在のノードの右ノードです。現在のノードは出力です（currentNode.right = null || currentNode.right == rightnode）{system.out.print（currentNode.Value + ""）; rightnode = currentNode; if（stack.isempty（））{return; //ルート出力、トラバーサルエンド} currentNode = stack.pop（）; } stack.push（currentNode）; // currentNode = currentNode.rightをトラバースしない正しいノードがまだあります。 }} / ***幅第一のトラバースバイナリツリー、階層トラバーサルバイナリツリー* @param node* / public void bredthfirsttraverse（node <e> root）{queue <node <e >> queue = new linkedlist <node <e >>（）; node <e> currentNode = null; queue.offer（root）; while（！queue.isempty（））{currentNode = queue.poll（）; System.out.print（currentNode.Value + ""）; if（currentnode.left！= null）queue.offer（currentNode.Left）; if（currentNode.right！= null）queue.offer（currentNode.right）; }}}②出力結果
事前注文トラバーサル（再帰）：35 20 15 16 29 28 30 40 50 45 55
順序トラバーサル（再帰）：15 16 20 28 29 30 35 40 45 50 55
延期トラバーサル（再帰）：16 15 28 30 29 20 45 55 50 40 35
事前注文トラバーサル（非再帰）：35 20 15 16 29 28 30 40 50 45 55
順序トラバーサル（非再帰）：15 16 20 28 29 30 35 40 45 50 55
延期トラバーサル（非再帰）：16 15 28 30 29 20 45 55 50 40 35
幅の優先順位トラバーサル：35 20 40 15 29 50 16 28 30 45 55
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。