[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현

Algorithm

[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현

건복치 2020. 11. 6. 16:12

4. 이진트리의 순회

이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미

이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다.

루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다.

루트를 방문하는 작업을 V
왼쪽 서브 트리 방문을 L
오른쪽 서브트리 방문을 R

루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회
루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회
루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다.

이진트리에서 각각의 서브 트리 역시 이진트리이다.

전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다.

-> 문제의 구조는 같고 크기만 작아지는 경우 -> 순환(재귀) 적용

전위 순회

루트 노드를 방문한다.
왼쪽 서브 트리를 방문한다.
오른쪽 서브트리를 방문한다.

중위 순회

왼쪽 서브트리를 방문한다.
루트 노드를 방문한다.
오른쪽 서브 트리를 방문한다.

후위 순회

왼쪽 서브 트리의 모든 노드를 방문한다.
오른쪽 서브트리의 모든 노드를 방문한다.
루트 노드를 방문한다.

5. Java로 구현

트리 입력

첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 )
두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며,
그 의미는 노드 a의 왼쪽 자식 노드가 b, 오른쪽 자식 노드가 c라는 뜻이다.
자식 노드가 존재하지 않을 경우에는 -1이 주어진다.

아래 예시 코드를 바탕으로 트리를 구성하겠습니다.

트리 표현하기

트리를 표현할 노드가 클래스 구조체로 표현된다.

하나의 노드는 데이터를 저장하는 필드, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 필드 총 3개의 필드를 가진다.

-> 노드 클래스 생성

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

트리를 클래스로 나타내는 것 말고 일차원, 이차원 배열로 나타내는 법을 알고 싶다면

[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현

본격적으로 트리를 구성하기 위해 트리 클래스를 만든다.

트리 클래스는 아래의 메서드들로 구성된다.

값을 추가하는 createNode() 메서드
값을 어느 위치에 추가할 것인지 찾기 위한 searchNode() 메서드
전위 순회(preOrder), 중위 순회(inOrder), 후위 순회(postOrder) 메서드

public class TreeOrderClass {
	public Node root; //초기 root는 null

	public void createNode(int data, int leftData, int rightData) {
	}

	public void searchNode(Node node, int data, int leftData, int rightData) { 
	}

	public void preOrder(Node node) {
	}

	public void inOrder(Node node) {
	}

	public void postOrder(Node node) {
	}
}

1. 값을 추가하는 createNode() 메서드

트리가 생성되기 전 초기 root 값은 null이다.

트리 생성을 통해 처음 루트 노드 객체가 생성되고 왼쪽, 오른쪽 값이 있느냐 없느냐에 따라 왼쪽, 오른쪽 역시 노드 객체가 생성된다.

루트 노드 생성 이후 추가되는 노드들은 어느 위치에 추가될지 판별해야 하기 때문에 serchNode() 메서드를 통해 탐색하게 된다.

public void createNode(int data, int leftData, int rightData) {
	if(root == null) { //초기 상태 - 루트 노드 생성 
		root = new Node(data);

		//좌우 값이 있는 경우, 즉 -1이 아닌 경우 노드 생성 
		if(leftData != -1) {
			root.left = new Node(leftData); //왼쪽 자식 노드 값을 가지는 Node 인스턴스 생성 
		}
		if(rightData != -1) {
			root.right = new Node(rightData); //오른쪽 자식 노드 값을 가지는 Node 인스턴스 생성 
		}
	} else { //초기 상태가 아니라면, 루트 노드 생성 이후 만들어진 노드 중 어떤건지를 찾아야함 
		searchNode(root, data, leftData, rightData);
	}
}

// 가장 처음 0 1 2 입력 - if(root == null)문에서 0이 루트 노드로 삽입

       0
      / \
     1   2
     
// 두 번째 1 3 4 입력 - else문에서 searchNode 메서드로 이동해 1 노드를 찾은 뒤 3, 4를 자식 노드로 삽입
       0
      / \
    (1)  2
    / \  
  (3) (4)

2. 값을 어느 위치에 추가할 것인지 찾기 위한 searchNode() 메서드

매개변수로 들어온 node(처음엔 root 노드가 들어있음)를 시작으로 data와 같은 값을 가지는 노드를 찾는다.

찾을 때까지 root노드에서부터 왼쪽, 오른쪽으로 내려간다.

찾는다면 들어갈 위치를 찾은 것임으로 왼쪽, 오른쪽 값이 있는 경우 그 노드의 왼쪽, 오른쪽 노드 객체를 생성한다.

null이라면 들어갈 위치를 찾지 못한 것임으로 재귀를 종료한다.

//매개변수로 들어온 root노드를 시작으로 data와 같은 값을 가진 node를 찾는다. 
//찾을 때까지 root노드에서 부터 왼쪽, 오른쪽으로 내려감 
public void searchNode(Node node, int data, int leftData, int rightData) { 
	if(node == null) { //도착한 노드가 null이면 재귀 종료 - 찾을(삽입할) 노드 X
		return;
	} else if(node.data == data) { //들어갈 위치를 찾았다면 
		if(leftData != -1) { //-1이 아니라 값이 있는 경우에만 좌우 노드 생성 
			node.left = new Node(leftData);
		}
		if(rightData != -1) {
			node.right = new Node(rightData);
		}
	} else { //아직 찾지못했고 탐색할 노드가 남아 있다면 
		searchNode(node.left, data, leftData, rightData); //왼쪽 재귀 탐색 
		searchNode(node.right, data, leftData, rightData); //오른쪽 재귀 탐색 
	}
}

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

//전위순회 Preorder : Root -> Left -> Right
public void preOrder(Node node) {
	if(node != null) {
		System.out.print(node.data + " ");
		if(node.left != null) preOrder(node.left);
		if(node.right != null) preOrder(node.right);
	}
}

//중위 순회 Inorder : Left -> Root -> Right
public void inOrder(Node node) {
	if(node != null) {
		if(node.left != null) inOrder(node.left);
		System.out.print(node.data + " ");
		if(node.right != null) inOrder(node.right);
	}
}

//후위순회 Postorder : Left -> Right -> Root
public void postOrder(Node node) {
	if(node != null) {
		if(node.left != null) postOrder(node.left);
		if(node.right != null) postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

전체 코드

import java.util.*;

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

public class TreeOrderClass {
	public Node root; //초기 root는 null

	public void createNode(int data, int leftData, int rightData) {
		if(root == null) { //초기 상태 - 루트 노드 생성 
			root = new Node(data);
			
			//좌우 값이 있는 경우, 즉 -1이 아닌 경우 노드 생성 
			if(leftData != -1) {
				root.left = new Node(leftData); //왼쪽 자식 노드 값을 가지는 Node 인스턴스 생성 
			}
			if(rightData != -1) {
				root.right = new Node(rightData); //오른쪽 자식 노드 값을 가지는 Node 인스턴스 생성 
			}
		} else { //초기 상태가 아니라면, 루트 노드 생성 이후 만들어진 노드 중 어떤건지를 찾아야함 
			searchNode(root, data, leftData, rightData);
		}
	}
	
	//매개변수로 들어온 root노드를 시작으로 data와 같은 값을 가진 node를 찾는다. 
	//찾을 때까지 root노드에서 부터 왼쪽, 오른쪽으로 내려감 
	public void searchNode(Node node, int data, int leftData, int rightData) { 
		if(node == null) { //도착한 노드가 null이면 재귀 종료 - 찾을(삽입할) 노드 X
			return;
		} else if(node.data == data) { //들어갈 위치를 찾았다면 
 			if(leftData != -1) { //-1이 아니라 값이 있는 경우에만 좌우 노드 생성 
 				node.left = new Node(leftData);
 			}
 			if(rightData != -1) {
 				node.right = new Node(rightData);
 			}
 		} else { //아직 찾지못했고 탐색할 노드가 남아 있다면 
 			searchNode(node.left, data, leftData, rightData); //왼쪽 재귀 탐색 
 			searchNode(node.right, data, leftData, rightData); //오른쪽 재귀 탐색 
 		}
	}
	
	
	//전위순회 Preorder : Root -> Left -> Right
	public void preOrder(Node node) {
		if(node != null) {
			System.out.print(node.data + " ");
			if(node.left != null) preOrder(node.left);
			if(node.right != null) preOrder(node.right);
		}
	}

	//중위 순회 Inorder : Left -> Root -> Right
	public void inOrder(Node node) {
		if(node != null) {
			if(node.left != null) inOrder(node.left);
			System.out.print(node.data + " ");
			if(node.right != null) inOrder(node.right);
		}
	}

	//후위순회 Postorder : Left -> Right -> Root
	public void postOrder(Node node) {
		if(node != null) {
			if(node.left != null) postOrder(node.left);
			if(node.right != null) postOrder(node.right);
			System.out.print(node.data + " ");
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		TreeOrderClass t = new TreeOrderClass();
		
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			t.createNode(a, b, c);
		}
        
        System.out.println("전위 순회");
        t.preOrder(t.root);
        
        System.out.println("\n중위 순회");
        t.inOrder(t.root);
        
        System.out.println("\n후위 순회");
        t.postOrder(t.root);
	}

}

출력

전위 순회
0 1 3 4 2 5 
중위 순회
3 1 4 0 2 5 
후위 순회
3 4 1 5 2 0

5. 반복적 순회

반복을 이용해서도 트리 순회를 할 수 있다.

스택(Stack)을 사용해 자식 노드들을 저장하고 꺼내면서 순회를 한다. -> 중위 순회 결과와 동일

(순환 호출도 사실은 시스템 스택을 사용하고 있는 것이기 때문에 별도의 스택을 사용하면 순환 호출을 흉내 낼 수 있음)

이진트리의 왼쪽 노드들을 null 노드에 도달할 때까지 스택에 추가한다.
null 노드에 도달하면 스택에서 하나씩 pop()을 통해 삭제한다.
삭제된 노드를 방문한다. (방문했다는 의미로 출력함)
방문 후 삭제된 노드의 오른쪽 노드로 이동한다.

이 오른쪽 노드를 다시 현재 노드로 스택이 빌 때까지 1~4를 반복을 하면 이진트리를 중위 순회할 수 있다.

* 트리 생성 및 메인 코드는 위에서 설명한 코드와 동일하고 iterativeOrder 함수만 추가된 것이다.

메인 함수에서 아래 코드를 추가해 실행하면 된다.

t.iterativeOrder(t.root);

public void iterativeOrder(Node curr) {
	Stack<Node> stack = new Stack<>(); // 반복적 순회를 위한 스택 생성 

	//처음엔 루트 노드부터 시작 
	while (curr != null || !stack.isEmpty()) { 
		//현재 노드의 왼쪽 노드들을 null에 도달할 때까지(마지막 왼쪽 자식 노드까지) 스택에 추가한다. 
		while (curr != null) {
			stack.push(curr);
			curr = curr.left;
		} 

		//null 노드에 도달하면 스택에서 하나씩 삭제한다. 
		curr = stack.pop(); 
		System.out.print(curr.data + " "); //삭제된 노드 방문 -> 삭제된 노드의 값 출력 

		//삭제된 노드를 방문한 후에 이 노드의 오른쪽 노드로 이동한다.
		curr = curr.right;
		//다시 이 노드를 기준으로 왼쪽 노드들을 null에 도달할 때까지 스택에 추가한다.
		// -> 이를 스택이 빌 때까지 반복하면 이진트리를 중위순회할 수 있다.
	}
}

6. 레벨 순회

각 노드를 레벨 순으로 검사하는 순회 방법

루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨이 증가한다.

동일한 레벨의 경우에는 좌에서 우로 이동한다.

큐를 사용한다.

큐에 하나라도 노드가 있으면 계속 반복하는 코드로 이루어져 있다.

먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로 한 번의 반복을 끝낸다.

이러한 반복을 큐에 더 이상의 노드가 없을 때까지 계속한다.

* 트리 생성 및 메인 코드는 위에서 설명한 코드와 동일하고 levelOrder, levelByLevel 함수만 추가된 것이다.

메인 함수에서 아래 코드를 추가해 실행하면 된다.

t.levelOrder(t.root);

t.levelByLevel(t.root);

//레벨 순회한 결과 출력 
public void levelOrder(Node root) {
	Queue<Node> queue = new LinkedList<>();
	queue.offer(root);

	while(!queue.isEmpty()) {
		Node node = queue.poll();
		System.out.print(node.data + " ");

		if(node.left != null) queue.offer(node.left); // 왼쪽 자식 노드가 있다면 추가 
		if(node.right != null) queue.offer(node.right); // 오른쪽 자식 노드가 있다면 추가 
	}
}

번외로 각 레벨별 노드를 출력한 코드이다.

//레벨별 노드들을 배열로 묶어서 출력 
public void levelByLevel(Node root) {
	ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // 전체 레벨을 담기 위한 ArrayList

	Queue<Node> queue = new LinkedList<>();
	queue.offer(root);

	while(!queue.isEmpty()) {
		ArrayList<Integer> level = new ArrayList<>(); //레벨 별 값을 담기 위한 ArrayList

		int size = queue.size();
		for(int i = 0; i < size; i++) {
			Node node = queue.poll();
			level.add(node.data); //큐에서 꺼낸 노드 level list에 저장 

			if(node.left != null) queue.offer(node.left); // 왼쪽 자식 노드가 있다면 추가 
			if(node.right != null) queue.offer(node.right); // 오른쪽 자식 노드가 있다면 추가 
		}

		list.add(level); // 한 레벨이 끝날 때마다 레벨별 저장된 값들을 전체 list에 저장 
	}

	for (ArrayList<Integer> i : list) {
		System.out.println(i);
	}
}

7. 전체 순회 코드

import java.util.*;

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

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

public class TreeOrderMaster {
	public Node root; //초기 root는 null

	public 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); 
			}
		} else { 
			searchNode(root, data, leftData, rightData);
		}
	}

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

	//전위순회 Preorder : Root -> Left -> Right
	public void preOrder(Node node) {
		if(node != null) {
			System.out.print(node.data + " ");
			if(node.left != null) preOrder(node.left);
			if(node.right != null) preOrder(node.right);
		}
	}

	//중위 순회 Inorder : Left -> Root -> Right
	public void inOrder(Node node) {
		if(node != null) {
			if(node.left != null) inOrder(node.left);
			System.out.print(node.data + " ");
			if(node.right != null) inOrder(node.right);
		}
	}

	//후위순회 Postorder : Left -> Right -> Root
	public void postOrder(Node node) {
		if(node != null) {
			if(node.left != null) postOrder(node.left);
			if(node.right != null) postOrder(node.right);
			System.out.print(node.data + " ");
		}
	}

	//반복적 순회 - Stack 사용 
	public void iterativeOrder(Node curr) {
		Stack<Node> stack = new Stack<>(); 

		while (curr != null || !stack.isEmpty()) { 
			while (curr != null) {
				stack.push(curr);
				curr = curr.left;
			} 
			curr = stack.pop(); 
			System.out.print(curr.data + " ");
			curr = curr.right;
		}
	}

	//레벨 순회 - Queue 사용 
	public void levelOrder(Node root) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);

		while(!queue.isEmpty()) {
			Node node = queue.poll();
			System.out.print(node.data + " ");

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

	//레벨별 노드 출력 
	public void levelByLevel(Node root) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<>(); 

		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);

		while(!queue.isEmpty()) {
			ArrayList<Integer> level = new ArrayList<>();

			int size = queue.size();
			for(int i = 0; i < size; i++) {
				Node node = queue.poll();
				level.add(node.data); 

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

			list.add(level);
		}

		for (ArrayList<Integer> i : list) {
			System.out.println(i);
		}
	}


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		TreeOrderMaster t = new TreeOrderMaster();

		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			t.createNode(a, b, c);
		}

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

		System.out.println("\n중위 순회");
		t.inOrder(t.root);

		System.out.println("\n후위 순회");
		t.postOrder(t.root);

		System.out.println("\n반복적 순회");
		t.iterativeOrder(t.root);

		System.out.println("\n레벨 순회");
		t.levelOrder(t.root);

		System.out.println("\n레벨별 노드");
		t.levelByLevel(t.root);
	}

}

출력

전위 순회
0 1 3 4 2 5 

중위 순회
3 1 4 0 2 5 

후위 순회
3 4 1 5 2 0 

반복적 순회
3 1 4 0 2 5 

레벨 순회
0 1 2 3 4 5 

레벨별 노드
[0]
[1, 2]
[3, 4, 5]

8. (참고) 노드의 개수, 단말 노드의 개수, 높이 구하기

1. 노드의 개수 구하기

노드의 개수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다.

각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환한다.

public static int getNodeCount(Node root) {
	int count = 0;

	if(root != null)
		count = 1 + getNodeCount(root.left) + getNodeCount(root.right);

	return count;
}

2. 단말 노드 개수 구하기

단말 노드의 개수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다.

순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 0이 되면 단말 노드이므로 1을 반환한다.

만약 그렇지 않다면 비 단말 노드이므로 각각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다.

public static int getLeafCount(Node root) {
	int count = 0;

	if(root != null) {
		if(root.left == null && root.right == null)
			return 1;
		else
			count = getLeafCount(root.left) + getLeafCount(root.right);
	}

	return count;
}

3. 높이 구하기

public static int getHeight(Node root) {
	int height = 0;

	if(root != null) 
		height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

	return height;
}

GITHUB

github.com/KwonMinha/Algorithm/tree/master/Tree/src

KwonMinha/Algorithm

Contribute to KwonMinha/Algorithm development by creating an account on GitHub.

github.com

티스토리