처음 퍼스트 검색

Question

나는 간단한 구현 쿼리를 가졌습니다.

그래서 나는 다음과 같은 코드를 사용하여 BST합니다

class Node{ 

    int data; 
    Node left=null; 
    Node right=null; 
    Node link=null; 

    public Node(int d) 
    { 
     data=d; 
    } 

    public void append(int d) 
    { 
     Node n=this; 
     Node nval=new Node(d); 
     if(n==null) 
     { 
      n.data=d; 
     } 
     else 
     { boolean done=false; 
      while(!done) 
      { 
       if(n.data<=d) 
       { 
        if(n.left==null) 
        { 
         n.left=nval; 
         done=true; 
        System.out.println("Data Entered "+nval.data); 
        } 
        else 
        { 
         n=n.left; 
        } 
       } 
       else 
       if(n.data>d) 
       { 
        if(n.right==null) 
        { 
         n.right=nval; 
         done=true; 
        System.out.println("Data Entered "+nval.data); 
        } 
        else 
        { 
         n=n.right; 
        } 
       } 
      } 
     } 
    } 
} 

지금, 내가 먼저 그것에 깊이 우선 검색 범위를 적용하기 시작했다. 나는이 일을하는 데 진짜 문제가있었습니다.

DFS의 경우 스택에 오른쪽으로 배치 된 현재 노드의 왼쪽 및 오른쪽 값을 추가해야합니까? 어떻게 프로그램 할 수 있을까요? 연결된 목록을 사용하여 문제가 발생 했습니까? 누군가가 데이터 구조 나 포인터가 어떻게되어야한다고 말할 수 있습니까?

동일한 문제가 BFS에서 발생합니다. 이전에 명확하지 않은 경우, 주요 문제는 배열 요소를 제거한 다음 해당 요소를 자식으로 대체하는 것입니다.

Answer 1

Queue (FIFO)은 일반적으로 BFS에서 잘 작동합니다. 그것은 우선 순위 큐가 될 필요는 없지만 종종 가중치를 부여하는 것은 매우 일반적이기 때문이다

큐 일반적으로하지만, FIFO (선입 선출) 방식으로 위해 요소 필요하지 않습니다. 제공된 비교 자 또는 요소의 자연 순서에 따라 요소를 정렬하는 우선 순위 대기열과 요소 LIFO (선입 선출)를 순서화하는 LIFO 대기열 (또는 스택)이 예외입니다. 순서가 무엇이든 관계없이 큐의 헤드는 remove() 또는 poll() 호출에 의해 제거되는 요소입니다. FIFO 대기열에서 모든 새 요소는 대기열의 끝에 삽입됩니다. 다른 종류의 대기열은 다른 배치 규칙을 사용할 수 있습니다. 모든 Queue 구현은 순서 지정 등록 정보를 지정해야합니다. 큐와 BFS에 대한

는 기본 "알고리즘"규칙 :

1. 넣어 초기 상태 (들) Q에서 (대기열)
2. 이 Q의 머리를 가지고
( remove 참조)
3. 취해진 값으로 무엇인가하십시오 (예 : parent -> [child1, child2 ..])
4. Q의 꼬리에 3 단계의 결과를 추가하십시오 (add 참조).)
5. Q 때까지 2 단계로 돌아갑니다이 비어 있거나 다른 쪽의 경우는

배열 그냥 피타 과거 초기화 및 반복 처리 할 수 ​​있습니다 얻을 수있다. "Slicing"과 "resizing"은 Java에서 특히 고통 스럽습니다.

DFS (FILO)에 대한

Answer 2

이 유는 첫째, 다음 왼쪽 아이에게 밀어, 각 노드의 스택

을 사용하여 스택에 그의 오른쪽 아이를 밀어 필요

BFS (FIFO)에 대한, U를 @pst 언급 된대로 큐를 사용해야합니다