프로그래밍 생활에서 우리는 항상 나무 구조를 만납니다. 지난 며칠 동안 우리는 트리 구조를 작동하기 만하면 자체 운영 방법과 프로세스를 기록합니다. 이제 이와 같은 나무가 있다고 가정 해 봅시다.
1. 깊이 우선 순위
영어 약어는 DFS, 즉 깊이의 첫 번째 검색입니다.
깊이 우선 검색은 개발 크롤러의 초기 단계에서보다 일반적으로 사용되는 방법입니다. 그 목적은 검색 된 구조의 리프 노드 (즉, 하이퍼 링크를 포함하지 않는 HTML 파일)에 도달하는 것입니다. HTML 파일에서 하이퍼 링크가 선택되면 링크 된 HTML 파일은 깊이 우선 검색을 수행합니다. 즉, 나머지 하이퍼 링크 결과를 검색하기 전에 별도의 체인을 전체적으로 검색해야합니다. 깊이 우선 순위 검색은 더 심화 될 수 없을 때까지 HTML 파일의 하이퍼 링크를 따르고 특정 HTML 파일로 돌아와서 HTML 파일에서 다른 하이퍼 링크를 계속 선택합니다. 다른 하이퍼 링크를 사용할 수 없으면 검색이 종료되었습니다. 프로세스는 더 깊이 더 깊을 수 없을 때까지 가능한 모든 분기 경로에 더 깊이 들어가는 것입니다. 각 노드는 한 번만 액세스 할 수 있습니다. 위의 예에서, 깊이 우선 순회 결과는 다음과 같습니다. 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 <string, object >> nodestack = now 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, 객체 >> 객체 >> wicks = getchildren (node); if (childs! = null &&! children.isempty ()) {for (map child : children) {nodestack.push (child);}}}}}}}}}}} // 노드는 MAP를 사용합니다.2. 폭이 우선 순위
영어 약어는 BFS이며, 이는 폭이 먼저 검색됩니다. 프로세스 테스트에 따르면, 각 노드 층에 차례로 액세스하고, 하나의 레이어에 액세스 한 후 각 노드는 한 번만 액세스 할 수 있습니다. 위의 예에서, 폭이 먼저 횡선의 결과는 다음과 같습니다.
폭은 우선 순위가 각 노드를 가로 지르고 큐와 같은 데이터 구조가 필요합니다. 대기열의 특성은 선 1 인, 선 1 인치이며 실제로는 이중 엔드 큐를 사용할 수도 있습니다. 차이점은 이중 종말 큐의 첫 번째 위치에서 노드를 삽입하고 팝업 할 수 있다는 것입니다. 전체 트래버스 프로세스는 다음과 같습니다.
먼저 큐에 노드 A를 삽입, 큐 (a);
노드 A를 팝업하고 자식 노드 B와 C를 대기열에 삽입하십시오. 이 시점에서 B는 대기열의 시작 부분에 있고 C는 대기열의 끝에 있으며, 대기열 (b, c);
노드 B를 팝업하고 B의 하위 노드 D와 E를 동시에 큐에 삽입하십시오. 이 시점에서 C는 대기열의 시작 부분에 있고 e는 큐의 끝에 있으며, 큐 (c, d, e);
노드 C를 팝업하고 하위 노드 F, G, H of C를 큐에 삽입하십시오. 현재, D는 대기열의 헤드에 있고 h는 대기열의 끝에 있으며, 큐 (d, e, f, g, h);
팝업 노드 D, D, D는 하위 노드가 없으며, 현재 e는 대기열의 헤드에 있으며, h는 큐의 꼬리, 대기열 (e, f, g, h);
... 차례로 아래로, 최종 트래버스가 완료됩니다. Java 코드는 다음과 같습니다.
public void breadfirst () {deque > nodedeque = 새로운 어레이 데크 > (); 지도 노드 = 새로운 해시 맵 (); nodedequ.add (노드); while (! nodedeque.isempty ()) {node = nodedequ.peekfirst (); System.out.println (노드); // 노드의 자식 노드를 가져옵니다. 이진 트리의 경우 왼쪽 하위 노드 및 노드의 오른쪽 하위 노드는 노드 목록을 얻는 것입니다. > 어린이 = GetChildren (노드); if (children! = null &&! children.isempty ()) {for (Map Child : children) {nodedequ.add (child); }}}} // 이중 엔드 큐는 여기에서 사용됩니다. 큐를 사용하는 것과 동일합니다. 요약
위의 내용은 깊이 우선 및 폭이 먼저 Java 구현 코드 예제에 대한이 기사의 모든 내용이며 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!