説明:

レベル単位でバイナリツリーをナビゲートして出力してください.

コード#コード#

class Node{
    int data;
    Node lt,rt;

    public Node(int val) {
        data = val;
        lt=rt = null;
    }
}
public class BFS {
    Node root;

    public static void main(String[] args) {
        BFS tree = new BFS();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.bfs(tree.root);
    }
    public void bfs(Node node){
        Queue<Node> que = new LinkedList<>();
        que.offer(node);
        int level = 0;
        while(!que.isEmpty()){
            System.out.println("level : "+level);
            int length = que.size();
            for(int i=0; i<length; i++){
                Node poll = que.poll();
                System.out.print(poll.data+" ");
                if(poll.lt != null) que.offer(poll.lt);
                if(poll.rt != null) que.offer(poll.rt);
            }
            System.out.println();
            level++;
        }
    }
}

これまでDFS(Depth First Search)を練習してきたなら、今回はBREADTH First Searchを練習します.DFSが実行時に最下位のノードを追跡し、最下位のノード間でナビゲートおよびダウングレードする方法である場合、BFSはノードをステップ別にナビゲートすることを意味する.

コードで実装ノードが上図と同じツリー構造データを有する場合、
DFSの場合

このような構造でツリーをナビゲートするとします.もちろん前尉中尉後尉によっても違いますが、詳細を検索して勉強することをお勧めします.
BFSの場合


上の図に示すように、手順に従います
ステップ0
1
ステップ1
2 3
ステップ2
4 5 6 7
探索を行う.では、コードを見てみましょう.
私たちは資料構造でQueueを使用して行い、queには出力する必要があるデータが含まれています.まずque最初のtreeRootを置いてから始まるTreeルートのデータ値は1なので、1から順にチェックします.すべてのツリーをチェックするために、queが空になるまで繰り返し、whileの繰り返し内部で繰り返し、ツリーのサブノードが存在するかどうかを決定します.

ステップ0
レベル=0の場合、queはルートの1つのデータしか存在しないため、sizeは1であり、for文は1回繰り返される.繰り返し文の内部で、queをポーリングしてroot値を返し、rootを返します.データの1が出力されます.まだ根があります.rtとroot.ltをチェックしnullでなければqueに追加します.最後にlevel++を追加します.

ステップ1
level=1の場合、queは最初に入力されたルートのltおよびrtデータを含み、rootはポーリングされて消失する.現在whileの条件でqueは空ではないので実行され、内部実行は0ステップと同じで、出力して23ステップ目に進みます.


ステップ2
level=2の場合、queに4つのデータがあり、4.5.67の順に出力されます.しかしながら、上記の繰り返しとは異なり、データのltおよびrtはnullであるため、queに値を与えず、queは最終的に空になり、したがって繰り返し文は終了する.
以上のすべてのステップが完了したら.

次の結果を結果ウィンドウに出力できます.
DFSとBFSの概念を正しく区別し,BFSの段階的探索方法を直接符号化とピクチャで記述することを学ぶ.