05-3 이진 트리의 구현 및 순회

※ 순차 자료구조 방식을 이용한 이진 트리 구현

 - 노드번호를 배열의 인덱스로 사용하여 1차원 배열로 표현한다.

   아래 그림에서 보듯 완전 이진 트리나 포화 이진트리가 아니면 메모리의 낭비가 생긴다.

**인덱스 규칙 (i = 인덱스, n= 노드의 수)

1. 노드 i의 부모 노드  = i/2 (단 i>1)
   
2. 노드 i의 왼쪽 자식 노드 = i*2 (단 i*2 <=n)
   
3. 노드 i의 오른쪽 자식 노드  = i*2 +1 (단 i*2+1 <= n)
   
4. 루트 노드 = 1 (단 0<n)

※ 연결 자료구조 방식을 이용한 이진 트리 구현

 - 배열을 이용한 순차 자료구조 방식은 구현이 쉽고 인덱스 규칙에 따라 자식노드를 찾기 쉽다. 그러나 메모리 낭비가 생길 수 있다. 그렇기 때문에 이런 메모리 낭비 문제와 삽입, 삭제 연산이 비효율적이라 연결 자료구조 방식을 많이 이용한다.

 - 노드는 오른쪽, 왼쪽 링크 필드로 구성, 자식노드가 없을 시 링크값은 null로 설정

 - 연결 자료구조를 이용한 트리구조

  

※ 이진 트리의 순회

 - 트리를 사용하여 자료를 계층적인 구조로 저장하고, 사용하기 위해서는 트리에 있는 모든 노드를 방문하는 방법이 필요하다.

    이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것을 순회(traversal)이라 한다.

    리스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지 였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러 가지 

    순회 방법이 있을 수 있다.

 - 현재 노드를 방문하여 데이터를 읽는 작업을 D, 현재 노드의 왼쪽 서브트리로 이동하는 작업L, 현재 노드의 오른쪽 서브트리로 이동하는 작업을 R로 정의한다.

 - 서브 트리는 항상 왼쪽부터 오른쪽으로 순회하고 현재 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있다.

※ 전위 순회(Preorder Traversal)

 - DLR의 순서로 순회하는 방법.

 - 현재 노드를 방문해 값을 확인한 후 왼쪽 서브트리 방문 후 오른쪽 서브트리를 방문한다.

 - 만약 지속적으로 왼쪽 서브트리 값이 있다면 왼쪽을 계속 방문한 후 마지막 왼쪽 서브트리에 도달한 후 순차적으로 올라가면서 오른쪽 노드를 방문한다.

전위 순회 알고리즘과 예시

※ 중위 순회(Inorder Traversal)

 - LDR의 순서로 순회하는 방법

 - 현재 노드의 왼쪽 방문 후 방문한 노드의 값을 학인한 후 오른쪽 노드를 방문한다.

 - 만약 지속적으로 왼쪽 서브트리 값이 있다면 왼쪽 노드를 계속 방문해 단말 노드까지 접근한다. 그런 후 단말 노드의 값을 확인한 후

   순차적으로 올라가면서 값을 확인하고 올라가는 길에 오른쪽 서브트리가 있는 노드를 만난다면 오른족 서브트리 방문 후 그 노드가

   왼쪽 노드가 있나 확인하고 있다면 다시 왼쪽 노드의 단말노드까지 접근 후 값 확인을 하면서 올라온다.

   즉 왼쪽 단말노드 접근 후 순차적으로 올라가면서 값 확인 -> 올라가는길에 오른쪽 노드가 있다면 오른쪽 노드 방문 후 왼쪽

   단말노드 접근 후 순차적으로 올라가면서 값 확인을 반복한다.

중위 순회 알고리즘과 예시

※ 후위 순회(Postorder Traversal)

 - LRD의 순서로 순회하는 방법

 - 왼쪽 단말 노드까지 방문을 하고 올라오면서 값을 확인한다. 그런 후 오른쪽 서브트리가 있는 노드를 방문하면 값을 확인하지 않고

   오른쪽 서브트리로 방문한다. 그런 후 왼쪽 단말노드까지 접근한 후 다시 값을 확인하고 왼쪽 노드 값을 다 확인하면 오른쪽 노드 값을 

   단말노드부터 올라오면서 확인한다. 그리고 분기점(공백노드가 없는 이진트리)에 값을 제일 나중에 확인한다.

후위 순회 알고리즘과 예시

※ 이진트리 소스로 구현하기

1. 연결 자료구조를 이용하여 트리를 만든다.
2. 트리는 순회 방법에 따라 전위 표기식, 중위 표기식, 후위 표기식을 구할 수 있다. 각각의 순회 방법을 이용해 모든 표기식으로 표현해보자
3. 식은 중위표기식 기준으로 A*B-C/D이다.

         

Node

public class Node {

       protected Node left;

       private Object data;

       protected Node right;

       public Node(Object data) {

              left =null;

              right =null;

              this.data = data;

       }

       public Object getData(){

              return this.data;

       }

}

BinaryTree

public class BinaryTree {

       private Node root;

       public BinaryTree() {

              this.root = null;

       }

       public Node makeBT(Node bt1, Object data, Node bt2){

              Node newNode = new Node(data);

              newNode.left = bt1;

              newNode.right =bt2;

              return newNode;

       }

       public void preorder(Node root){

              if(root != null){

                     System.out.print(root.getData());

                     preorder(root.left);

                     preorder(root.right);

              }

       }

       public void inorder(Node root){

              if(root != null){

                     inorder(root.left);

                     System.out.print(root.getData());

                     inorder(root.right);

              }

       }

       public void postorder(Node root){

              if(root != null){

                     postorder(root.left);

                     postorder(root.right);

                     System.out.print(root.getData());

              }

       }

}

Main

public class Main {

       public static void main(String[] args) {

              BinaryTree bt = new BinaryTree();

              Node n7 = bt.makeBT(null, "D", null);

              Node n6 = bt.makeBT(null, "C", null);

              Node n5 = bt.makeBT(null, "B", null);

              Node n4 = bt.makeBT(null, "A", null);

              Node n3 = bt.makeBT(n6, "/", n7);

              Node n2 = bt.makeBT(n4, "*", n5);

              Node n1 = bt.makeBT(n2, "-", n3);

              System.out.print("preorder : ");

              bt.preorder(n1);

              System.out.println();

              System.out.print("inorder : ");

              bt.inorder(n1);

              System.out.println();

              System.out.print("postorder : ");

              bt.postorder(n1);

              System.out.println();

       }

}