Tree (트리) - 2

배열을 이용한 이진 트리의 표현

• 이진 트리에 각 노드 번호를 다음과 같이 부여
• 루트의 번호를 1로 함
• 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n부터 2^(n+1) -1까지 번호를 차례대로 부여

 

 

배열을 이용한 이진 트리의 표현

 

노드 번호의 성질

노드 번호가 i인 노드의 부모 번호는 i / 2

노드 번호가 i인 노드의 왼쪽 자식 노드 번호는 2 * i

노드 번호가 i인 노드의 오른쪽 자식 노드 번호는 2 * i + 1

레벨 n의 노드 번호 시작 번호는 2^n

노드 번호를 배열의 인덱스로 사용,

레벨 i의 최대 노드 수는 2^i

높이가 h인 이진 트리를 위한 배열의 크기는 2^(h+1)+1

 

배열을 이용한 이진 트리 표현의 단점

편향이진트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생

트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경이 어렵기 때문에 비효율적이다.

 

이진트리 순회(traversal)

순회(traversal): 트리의 노드들을 체계적으로 방문하는 것

전위순회(preorder traversal): VLR

 - 부모노드 방문 호, 자식노드를 좌, 우 순서로 방문한다. 

중위순회(inorder traversal): LVR

 - 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문한다.

후위순회(postorder traversal): LRV

 - 왼쪽 자식노드, 오른쪽 자식노드, 부모노드 순으로 방문한다. 

 

전위순회(preorder traversal)

현재 노드 T를 방문하여 처리한다. -> V

현재 노드 T의 왼쪽 서브트리로 이동한다 -> L

현재 노드 T의 오른쪽 서브트리로 이동한다. -> R

void printPreorder(Node node)
    {
        if (node == null)
            return;
 
        /* first print data of node */
        System.out.print(node.key + " ");
 
        /* then recur on left sutree */
        printPreorder(node.left);
 
        /* now recur on right subtree */
        printPreorder(node.right);
    }

 

중위순회(inorder traversal)

현재 노드 T의 왼쪽 서브트리로 이동한다. -> L

현재 노드 T를 방문하여 처리한다. -> V

현재 노드 T의 오른쪽 서브트리로 이동한다. -> R

void printInorder(Node node)
    {
        if (node == null)
            return;
 
        /* first recur on left child */
        printInorder(node.left);
 
        /* then print the data of node */
        System.out.print(node.key + " ");
 
        /* now recur on right child */
        printInorder(node.right);
    }

 

 

후위순회(postorder traversal)

현재 노드 T의 왼쪽 서브트리로 이동한다. -> L

현재 노드 T의 오른쪽 서브트리로 이동한다. -> R

현재 노드 T를 방문하여 처리한다. -> V

void printPostorder(Node node)
    {
        if (node == null)
            return;
 
        // first recur on left subtree
        printPostorder(node.left);
 
        // then recur on right subtree
        printPostorder(node.right);
 
        // now deal with the node
        System.out.print(node.key + " ");
    }