성장일기

[Java] 2. 트리(Tree) 구현과 순회 JAVA

Coding Test/Algorithms
2021. 11. 20. 07:00

트리를 구현하는 방법은 크게 3가지가 있다.

  1. 1차원 배열을 이용
  2. 2차원 배열을 이용
  3. 노드(클래스)를 이용

 트리를 구현하는 방법 중 배열을 이용한 방법은 배열의 크기가 정해져있기 때문에 한계가 있다. 따라서 코딩테스트에서 문제를 풀때 많이 활용되지 않을것으로 생각돼서 노드(클래스)를 이용한 구현방법과 순회를 정리하려고 한다.

 

 

1. 트리를 구성하는 노드 클래스

class Node { //트리의 노드 정보를 저장할 클래스 
	int data; //노드 값 
	Node left; //왼쪽 자식 노드 참조 값 
	Node right; //오른쪽 자식 노드 참조 값 
	
	//추가할 때 참조되는 왼쪽, 오른쪽 자식의 값은 모르닌까 일단 data 값을 기반으로 Node 객체 생성 
	Node(int data){ 
		this.data = data;
	}
}

 

 

2. 트리를 생성하고 순회하는 역할을 하는 클래스

 

2.1 노드를 추가하는 createNode() 메소드

2.2 노드를 어느 위치에 추가할 것인지를 찾는 searchNode() 메소드

public static void createNode(int data, int leftData, int rightData) {
        if (root == null) {
            root = new Node(data);

            if (leftData != -1) {
                root.left = new Node(leftData);
            }
            if (rightData != -1) {
                root.right = new Node(rightData);
            }
        }
        searchNode(root, data, leftData, rightData);
    }

    public static void searchNode(Node node, int data, int leftData, int rightData) {
        if (node == null) {
            return;
        }
        if (node.data == data) {
            if (leftData != -1) {
                node.left = new Node(leftData);
            }
            if (rightData != -1) {
                node.right = new Node(rightData);
            }
        }
        searchNode(node.left, data, leftData, rightData);
        searchNode(node.right, data, leftData, rightData);
    }

 

 

2.3 전위 순회(preOrder), 중위 순회(inOrder), 후위 순회(postOrder) 메서드

 이진트리를 루트노드, 왼쪽 서브트리, 오른쪽 서브트리로 나누어서  차례로 순회한다.(루트 노드를 기준으로 잡으면 쉽다.)

  1. 전위 순회(preOrder): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  2. 중위 순회(inOrder): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
  3. 후위 순회(postOrder): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
  4. 레벨 순회(levelOrder): 레벨 0부터 끝까지 차례대로 순회

 

순회 예시

preOrder: 5 -> 3 -> 2 -> 5 -> 7 -> 8

inOrder: 2 -> 3-> 5-> 5-> 7 -> 8

postOrder: 2 -> 5 -> 3-> 8 -> 7 -> 5

levelOrder: 5 -> 3 -> 7 -> 2 -> 5 -> 8

 

 

 

 

 

 

 

// 전위순회 루트 -> 왼쪽 -> 오른 = 깊이우선탐색
    public static void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    //전위순회 스택으로 구현해보기
    public static void preOrder2(Node node) {
        Deque<Node> dq = new LinkedList<>();

        dq.offerLast(node);

        while (!dq.isEmpty()) {
            Node pNode = dq.pollLast();

            System.out.print(pNode.data + " ");
            if (pNode.right != null) {
                dq.offerLast(pNode.right);
            }
            if (pNode.left != null) {
                dq.offerLast(pNode.left);
            }
        }
    }

    // 중위순회 왼쪽 -> 루트 -> 오른
    public static void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    // 후위순회 왼쪽 -> 오른쪽 -> 루트
    public static void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    // 레벨순회 각 레벨에 맞게 순회 = 너비우선탐색
    public static void levelOrder(Node node) {

        Queue<Node> q = new LinkedList<>();

        q.offer(node);

        while (!q.isEmpty()) {
            Node pNode = q.poll();

            System.out.print(pNode.data + " ");

            if (pNode.left != null) {
                q.offer(pNode.left);
            }
            if (pNode.right != null) {
                q.offer(pNode.right);
            }

        }

    }

 

 

3. 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TreePractice {

    static Node root;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int a, b, c;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            createNode(a, b, c);
        }



        //전위순회
        preOrder(root);
        System.out.println();

        //전위순회2
        preOrder2(root);
        System.out.println();

        //중위순회
        inOrder(root);
        System.out.println();

        //후위순회
        postOrder(root);
        System.out.println();

        //레벨순회
        levelOrder(root);


    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public static void createNode(int data, int leftData, int rightData) {
        if (root == null) {
            root = new Node(data);

            if (leftData != -1) {
                root.left = new Node(leftData);
            }
            if (rightData != -1) {
                root.right = new Node(rightData);
            }
        }
        searchNode(root, data, leftData, rightData);
    }

    public static void searchNode(Node node, int data, int leftData, int rightData) {
        if (node == null) {
            return;
        }
        if (node.data == data) {
            if (leftData != -1) {
                node.left = new Node(leftData);
            }
            if (rightData != -1) {
                node.right = new Node(rightData);
            }
        }
        searchNode(node.left, data, leftData, rightData);
        searchNode(node.right, data, leftData, rightData);
    }

    // 전위순회 루트 -> 왼쪽 -> 오른 = 깊이우선탐색
    public static void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    //전위순회 스택으로 구현해보기
    public static void preOrder2(Node node) {
        Deque<Node> dq = new LinkedList<>();

        dq.offerLast(node);

        while (!dq.isEmpty()) {
            Node pNode = dq.pollLast();

            System.out.print(pNode.data + " ");
            if (pNode.right != null) {
                dq.offerLast(pNode.right);
            }
            if (pNode.left != null) {
                dq.offerLast(pNode.left);
            }
        }
    }

    // 중위순회 왼쪽 -> 루트 -> 오른
    public static void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    // 후위순회 왼쪽 -> 오른쪽 -> 루트
    public static void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    // 레벨순회 각 레벨에 맞게 순회 = 너비우선탐색
    public static void levelOrder(Node node) {

        Queue<Node> q = new LinkedList<>();

        q.offer(node);

        while (!q.isEmpty()) {
            Node pNode = q.poll();

            System.out.print(pNode.data + " ");

            if (pNode.left != null) {
                q.offer(pNode.left);
            }
            if (pNode.right != null) {
                q.offer(pNode.right);
            }

        }
    }
}

 

'Coding Test > Algorithms' 카테고리의 다른 글

[Java] 구간 합(Prefix Sum)  (0) 2022.01.18
[Java] 투 포인터(Two Pointers)  (0) 2022.01.18
[Java] 1. 트리의 개념 JAVA  (0) 2021.11.19
[Java] 덱 직접 구현하기 & 라이브러리 사용 JAVA  (0) 2021.11.15
[Java] 큐 직접 구현하기 & 라이브러리 사용 JAVA  (0) 2021.11.15

공유하기

facebook twitter kakaoTalk kakaostory naver band

'Coding Test/Algorithms' 의 관련글

티스토리툴바