幅優先トラバースはバイナリ ツリーのトラバースとどのように似ていますか?

幅優先トラバーサルは、バイナリ ツリーのレベル トラバーサルに似ています。幅優先検索はルート ノードから開始し、ツリーの幅に沿って検索および横断します。つまり、階層的に横断します。各レイヤーを上から下に順番に、各レイヤー内で左から右 (または右から) にアクセスします。左へ) をクリックしてノードにアクセスし、1 つのレベルにアクセスした後、アクセスできるノードがなくなるまで次のレベルに入ります。

幅優先検索 (実際にはバイナリ ツリーの階層走査)、幅優先検索または水平優先検索とも呼ばれ、ルート ノードから開始されます。ツリーの幅に沿った検索トラバース。

各層に上から下に順番にアクセスします。各層では、左から右 (または右から左) にノードにアクセスします。1 つの層にアクセスした後、アクセスできるノードがなくなるまで次の層に入ります。

上記のバイナリ ツリーの走査順序は ABCDEFG です。キューを使用して幅優先検索を実装できます。

幅優先検索アルゴリズム:

すべてのノードを保持し、多くのスペースを占有します。バックトラック操作なし (つまり、プッシュまたはポップ操作なし)、高速な実行速度です。 。

幅優先探索アルゴリズムは、一般に生成されたすべてのノードを保存する必要があり、占有される記憶領域は深さ優先探索よりもはるかに大きいため、プログラミング中にオーバーフローとメモリ領域の問題が発生します。節約を考慮する必要があります。ただし、幅優先検索方法には通常、バックトラッキング操作 (プッシュ操作やポップ操作) がないため、深さ優先検索よりも高速に実行されます。

例:

プロセス検査では、ノードの各層を順番に訪問し、訪問を完了します。 1 つのレイヤー 次のレベルに進むと、各ノードには 1 回だけアクセスできます。上記の例の場合、幅優先トラバーサルの結果は次のとおりです: A、B、C、D、E、F、G、H、I (各層のノードが左から右にアクセスされると仮定します)。

各ノードの幅優先トラバースには、キュー (Queue) データ構造の使用が必要です。キューの特性は先入れ先出しです。実際、両端キューも使用できます。違いは、両端キューの最初の位置を挿入してノードをポップアップできることです。トラバーサル プロセス全体は次のとおりです。

最初に A ノードをキュー queue(A) に挿入します。

A ノードをポップアップし、A の子ノード B と B を挿入します。 C をキューに追加します。この時点では、B はキューの先頭にあり、C はキューの最後にあります。 queue (B, C);

B ノードをポップし、B の子ノードを挿入します。 D と E をキューに追加します。このとき、C はキューの先頭にあります。E はキューの最後にあります。queue (C, D, E);

C ノードをポップし、 C の子ノード F、G、H をキューに挿入します。このとき、D がキューの先頭、H がキューの最後尾になります。キューの最後尾は、queue (D, E) , F, G, H);

D ノードをポップします。D には子ノードがありません。この時点では、E はキューの先頭にあり、H はキューの最後にあります。queue (E, F、G、H);

...順番に下に進み、最後の走査が完了します

Java コードはおおよそ次のとおりです:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
		}
        return lists;
    }
}

関連知識の詳細については、PHP中文网 をご覧ください。

以上が幅優先トラバースはバイナリ ツリーのトラバースとどのように似ていますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。