[JAVA] 재귀 - 이진트리(Binary Tree)의 순회

앞에 글에서 이진탐색트리의 삽입을 구현했었다.

이진탐색트리 삽입 (1) -  http://marobiana.tistory.com/81

이진탐색트리 삽입 (2) -  http://marobiana.tistory.com/82

이번에는 순회에 대해 짜볼 것이다.

사실 이걸 정리하고 싶었을 뿐인데, 이진탐색트리 삽입이 더 복잡해서 거기서 시간 다보냄 ㅎㅎ

요번건 소스가 아주 간단함.

1. 이진트리 순회 방법

컴공 2학년 때 자료구조에서 배우는 요것..

순회 방법에는 3가지가 있다.

각 순회방법으로 갔을 때 순서를 적어보겠다.

- Pre order (전위) : Root부터 왼쪽 모든 노드 탐색 후 오른쪽

24 15 2 19 28 27 30 

- In order (중위) : 맨 왼쪽 아래노드부터 Root, 오른쪽

2 15 19 24 27 28 30

- Post order (후위) : 맨 왼쪽 아래노드부터 오른쪽 탐색 후 Root

2 19 15 27 30 28 24

완전트리로 이해했다고 다 이해한건 아니다. 

불균형이진트리로 이해해야 진짜 이해임.

아래 트리를 보자.

- Pre order (전위)

A B D H E I C F G J K

- In order (중위)

H D B I E A F C J G K

- Post order (후위)

H D I E B F J K G C A

그림과 답을 따라가보면서 규칙을 찾으면 된다.

2. 예제

문제 : 이진트리의 전위 중위 후위 순회를 구현하라

http://marobiana.tistory.com/82 

여기서 만들었던 소스에다가 메소드들만 추가할 것이다.

트리 삽입 및 출력

public class BinarySearchTree {          public static void main(String[] args) { Tree tree = new Tree(); tree.addNode(24); tree.addNode(15); tree.addNode(19); tree.addNode(2); tree.addNode(28); tree.addNode(27); tree.addNode(30);                 System.out.print("PreOrder : ");       tree.preOrder(tree.root);              System.out.print("InOrder : ");      tree.inOrder(tree.root);      System.out.print("PostOrder : ");      tree.postOrder(tree.root); } }

Node

각각의 노드에 대한 속성이 담긴 클래스

여기는 그대로 ㅎㅎ

public class Node { private int value;  private Node left; private Node right; // Setter and Getter         ...... }

Tree

위에서 만든 노드들을 이어서 하나의 트리를 만드는 클래스

여기서 트리 순회한 것을 출력

public class Tree { public Node root; public void addNode(int value) { // 앞 글 참고 } public void addNode(int value, Node root) { // 앞 글 참고 } public void preOrder(Node root) { if (root == null) return; System.out.print(root.getValue() + " ");      preOrder(root.getLeft());      preOrder(root.getRight()); } public void inOrder(Node root) { if (root == null) return; inOrder(root.getLeft());      System.out.print(root.getValue() + " ");      inOrder(root.getRight()); } public void postOrder(Node root) { if (root == null) return; postOrder(root.getLeft());      postOrder(root.getRight());      System.out.print(root.getValue() + " "); } }

>> 결과

PreOrder : 24 15 2 19 28 27 30 InOrder : 2 15 19 24 27 28 30 PostOrder : 2 19 15 27 30 28 24

이상으로 재귀에 대한 포스팅을 마치겠음.

재귀는 실무에서 잘 쓰이지 않는다.

어렵기도 하고, 무리가 많이 가기 때문이다.

특히나 시스템쪽에서는 재귀호출은 금기시 하고 있다고 한다.

그런데 정리해본 이유는 함수가 함수를 부를 때 내부적으로 어떻게 돌아가는지 알고,

흐름은 알아야 하기 때문이다.

재귀에서 가장 중요한 포인트는 Return 타이밍이다.

어떻게 타고 들어가는지, 무엇이 리턴되었는지를 알고 적절히 끝낼 줄 알아야 한다.