Java의 이진 검색 트리에서 수준 순회를 구현하려고 시도했습니다.

Question

좋아, 그래서 노드에 int 값을 전달하는 기본 이진 검색 트리의 레벨 순서를 반환하는 메서드를 만들려고합니다. 나는 그런 삽입, 포스트 위해 사전 순서와 다른 방법의 대부분을 알아 냈어요,하지만 레벨 주문 방법 여기

와 같은 문제로 실행 계속 코드입니다 :

private DoubleStackQueue<Node> queue = new DoubleStackQueue<Node>(); 
//this is a queue that uses two stacks, one for the front and one for the back. 
//it works just like a queue. 
public String levelOrder(){ 
    s = ""; //The s is a private String that is implemented earlier 
    queue.add(this); 
    while (!queue.isEmpty()) 
    { 
     Node node = (Node)queue.remove(); 
     if (!(node.equals(null))) {s += ""+node.getVal();} 
     if (!(left.equals(null))) {queue.add(node.left);} 
     if (!(right.equals(null))) {queue.add(node.right);} 
    } 
    return s; 
} 

내가 겪고있는 주된 문제는 프로그램이 잎 노드에 도착할 때 자식 노드가 없어도 null을 계속해서 큐에 추가한다는 것입니다. 그래서 앞에서 두 개의 null이있는 큐를 가져옵니다. 실제 아이템의 나는 원래 if 문을 (왼쪽! = null) 등으로 가지고 있지만 그 중 하나는 작동하지 않았습니다. 저는 아이들이 없을 때 프로그램이 어떻게 인식되는지 알아 내려고합니다. 내가 무엇을해야 하나? 코드 내에서

Answer 1

여러 의견 :

1. 주요 문제는 당신이 당신의 비교에서 left 및 right 대신 node.left 및 node.right를 사용하고 있다는 점이다.

2. null과 비교하려면 if (var != null)을 사용하십시오. equals()을 사용하지 마십시오. 변수가 null 인 경우 NullPointerException을 트리거하는 메소드가 호출 될 수 없습니다.

3. 코드를 수정하면 null이 대기열에 삽입되지 않습니다. 추가하는 첫 번째 객체는 null이 아니므로 항상 this이며, 이후에는 항목을 대기열에 삽입하기 전에 항상 null을 확인합니다. 즉, 첫 번째 if (node != null) 수표가 필요하지 않습니다.

4. (Node) queue.remove()의 캐스트는 불필요합니다. 컴파일러가이 사실에 대해 경고해야합니다.

결과 :

queue.add(this); 

while (!queue.isEmpty()) 
{ 
    Node node = queue.remove(); 

    s += "" + node.getVal(); 

    if (node.left != null) { queue.add(node.left); } 
    if (node.right != null) { queue.add(node.right); } 
} 

Answer 2

나는 선 상태에서 아무데도 당신이 보여주는 부분으로 정의되지하지만, 오른쪽은 node.left 및 node.right 읽고 있습니다 left 및 right을 명시

if (!(left.equals(null))) {queue.add(node.left);} 
if (!(right.equals(null))) {queue.add(node.right);} 

을 찾을 수 있습니다. 의도적인가? if 조건에서도 node.left 및 node.right을 기대합니다.

Answer 3

이 질문을보십시오 : Level-order tree traversal 나는 이것이 당신이 달성하려고하는 것과 똑같은 것이라고 생각합니다. 그렇지 않습니까? 이것은 꽤 고전적인 문제입니다. 그래서 제 경험에서 이전에 반복해서 논의되었습니다.