JAVA 자료구조 : 이진검색트리 순회

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : 이진검색트리 순회

주어진 코드 중 levelOrder 메소드를 완성하라.

이진검색트리 순회란,

너비 우선 탐색(Breadth-first search) 이라고도 한다.

이진검색트리 순회의 검색순서는 트리 노드의 각 단계별로 좌에서 우로 & 위에서 아래로 찾아간다.

이진검색트리의 최상단부를 가리키는 root라는 포인터를 부여받고, 

맨 위에서부터 노드의 숫자를 출력한 뒤 그다음 레벨로 내려가서 맨 왼쪽부터 오른쪽으로 가면서 순서대로 노드의 숫자를 출력시킨다.

힌트 : 큐(Queue)의 원리를 이용해라.

검색순서 : 

※ 주어진 코딩

지정한 영역에서만 코딩하시오

import java.util.*;
import java.io.*;
class Node{
    Node left,right;
    int data;
    Node(int data){
        this.data=data;
        left=right=null;
    }
}
class Solution{
    static void levelOrder(Node root){
      * Write your code here *
    }
    public static Node insert(Node root,int data){
        if(root==null){
            return new Node(data);
        }
        else{
            Node cur;
            if(data<=root.data){
                cur=insert(root.left,data);
                root.left=cur;
            }
            else{
                cur=insert(root.right,data);
                root.right=cur;
            }
            return root;
        }
    }
    public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            int T=sc.nextInt();
            Node root=null;
            while(T-->0){
                int data=sc.nextInt();
                root=insert(root,data);
            }
            levelOrder(root);
    }    
}

입력

6

3

5

4

7

2

1

출력

3 2 5 1 4 7 

디버깅

맨 첫번째로 추가된 노드가 root포인터로 지정된다. ① root 포인터가 가리키는 3을 먼저 출력하고, 그 다음 단계의 왼쪽에 있는 노드데이터 출력하고, 오른쪽에 있는 노드데이터를 출력한다. 더이상 출력할 노드가 없다면 다음 단계로 내려간다. ② 이미 출력이 된 노드 중에(①단계 root포인터 하위노드) 맨 왼쪽 노드를 root 포인터로 잡고, 그 밑으로 가지를 치고 있는, 즉 root밑의 단계의 맨 왼쪽 노드데이터를 출력하고, 그 다음오른쪽 노드데이터를 출력한다. ③ root포인터 상위단계에 있는 노드 중 오른쪽 노드(①단계 root포인터 하위노드 중 오른쪽 노드) 를 root포인터로 잡는다. 그리고 그 root포인터 노드 아래단계의 맨 왼쪽노드데이터, 오른쪽노드데이터 순으로 데이터를 출력한다. 이러한 방식으로 반복을 하면 될 것 같고.. 이거를 로직으로 어떻게 짤까..? 그런데 힌트에서 큐(Queue) 원리를 이용하라고 했다.. 큐는 First In First Out.

결과

public class Node { public Node left, right; public int data; public Node(int data){ this.data=data; left=right=null; } } static void levelOrder(Node root){ Queue<Node> queue = new LinkedList(); queue.add(root); while(!queue.isEmpty()){ Node current = queue.remove(); System.out.print(current.data+" "); if (current.left!=null) queue.add(current.left); if (current.right!=null) queue.add(current.right); } } public static Node insert(Node root,int data){ if(root==null){ return new Node(data); }else{ Node cur; if(data<=root.data){ cur=insert(root.left,data); root.left=cur; }else{ cur=insert(root.right,data); root.right=cur; } return root; } } //end method insert public static void main(String[] args) { Scanner sc=new Scanner(System.in); int T=sc.nextInt(); Node root=null; while(T-->0){ int data=sc.nextInt(); root=insert(root,data); } //end while levelOrder(root); } //end method main

입력 :  7 3 5 4 7 2 1 8 결과 :  3 2 5 1 4 7 8

해석

line 11 : 자바에서 큐를 사용하기 위해 Queue 클래스와 LinkedList클래스를 import 해 온다. 제네릭은 Node클래스로 지정하여 Node클래스타입만 들어가도록 한다.

line 12 : Queue.add() 메소드로 큐에다가 root클래스를 추가한다.

line 14 : 큐에 요소가 모두 소진될때까지 while문으로 반복.

line 15 : Queue.remove() 메소드로 add된 요소를 Node변수(포인터)를 새로 정의해서 집어넣은 뒤 큐에서 제거시킨다.

line 17 : 큐에서는 요소가 제거 된 상태이지만 Node변수(포인터)에 남아있는 클래스의 left클래스가 존재한다면 해당 클래스(current.left)를 Queue에 추가시킨다.

line 18 : 마찬가지로 Node변수(포인터)의 right클래스가 존재한다면 해당 클래스(current.right)를 Queue에 추가시킨다.

line 17~18의 순서를 뒤바꾸면, 맨위의 노드를 제외 오른쪽에서 왼쪽으로 위에서 아래로 출력이 된다. ( 3 5 2 7 4 1 8 )