너비 우선 순회는 이진 트리 순회와 어떻게 유사합니까?

너비 우선 순회는 이진 트리의 수준 순회와 유사합니다. 너비 우선 검색은 루트 노드에서 시작하여 트리의 너비를 따라 검색하고 순회합니다. 즉, 계층적으로 순회합니다. 즉, 각 계층을 위에서 아래로 순차적으로 방문하고 각 계층에서는 왼쪽에서 오른쪽(또는 오른쪽에서 오른쪽)으로 방문합니다. 왼쪽) 노드에 접근하고, 한 레벨에 접근한 후 더 이상 접근할 수 없는 노드가 있을 때까지 다음 레벨로 입장합니다.

너비 우선 검색(실제로는 이진 트리의 계층적 순회)은 너비 우선 검색 또는 수평 우선 검색이라고도 하며 루트 노드부터 시작하여 트리 너비를 따라 검색하고 순회합니다.

위에서 아래로 차례로 각 레이어에 액세스합니다. 각 레이어에서는 왼쪽에서 오른쪽으로(또는 오른쪽에서 왼쪽으로) 노드에 액세스합니다. 이제까지 노드가 더 이상 방문하지 않을 때까지 다음 레이어로 들어갑니다.

위 이진 트리의 순회 순서는 ABCDEFG입니다. 대기열을 사용하여 너비 우선 검색을 구현할 수 있습니다.

폭 우선 검색 알고리즘:

모든 노드를 유지하고 많은 공간을 차지합니다. 역추적 작업이 없으며(예: 푸시 또는 팝 작업 없음) 실행 속도가 빠릅니다.

폭 우선 검색 알고리즘은 일반적으로 생성된 모든 노드를 저장해야 하며, 차지하는 저장 공간이 깊이 우선 검색보다 훨씬 크기 때문에 프로그래밍 시 오버플로 및 메모리 공간 절약 문제를 고려해야 합니다. . 그러나 너비 우선 탐색 방법은 일반적으로 역추적 연산, 즉 푸시(push)와 팝(pop) 연산이 없기 때문에 깊이 우선 탐색보다 빠르게 실행됩니다.

예:

프로세스 검사는 한 레이어를 방문한 후 다음 레이어로 이동하며 각 노드는 한 번만 방문할 수 있습니다. 위의 예에서 너비 우선 순회 결과는 A, B, C, D, E, F, G, H, I입니다(각 계층의 노드는 왼쪽에서 오른쪽으로 액세스한다고 가정).

각 노드의 너비 우선 순회에는 대기열(Queue) 데이터 구조를 사용해야 합니다. 대기열의 특성은 실제로 이중 종료 대기열을 사용할 수도 있습니다. 해당 노드는 이중 종료 대기열의 맨 위에 삽입되고 튀어나올 수 있습니다. 전체 순회 과정은 다음과 같습니다.

먼저 노드 A를 대기열(A)에 삽입합니다.

노드 A를 팝아웃하고, 이때 B는 대기열에 삽입됩니다. 큐의 선두와 C는 큐의 시작 부분에 있습니다. 큐의 꼬리, 큐(B, C)

노드 B를 팝하고 이때 B의 하위 노드 D와 E를 큐에 삽입합니다. 대기열의 선두에 있고 E는 대기열의 끝에 있습니다. 대기열 (C, D, E) ;

노드 C를 팝업하고 C의 하위 노드 F, G, H를 대기열에 삽입합니다. 이번에는 D가 대기열의 시작 부분에 있고 H가 대기열의 끝 부분에 있습니다(D, E, F, G, H).

D 노드에는 하위 노드가 없습니다. 시간에 E는 대기열의 시작 부분에 있고 H는 대기열의 끝 부분에 있습니다(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 중국어 웹사이트의 기타 관련 기사를 참조하세요!