비선형 자료구조 - 이진 트리(Binary Tree) 구현과 순회

이진 트리 구현.

배열 : 레벨 순회 순으로 배열에 구성
연결 리스트 : 값과 간선을 관리하기 위한 연결리스트 구성

 

이진 트리의 순회(Traversal).

모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
전위/중위/후위 순회, 레벨순회로 분류할 수 있다.

 

전위 순회(preorder traversal)

순서 : 부모 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 노드를 방문
경로 : A → B → D → H → I → E → J → C → F → G
1. 현재 노드 A 출력 → A의 왼쪽 노드 B 출력 → B의 왼쪽 노드 D 출력 → D의 왼쪽 노드 H 출력 (하위 노드 없음)
2. D의 오른쪽 노드 I 출력 → B의 오른쪽 노드 E 출력 -> E의 왼쪽 노트 J 출력 (하위 노드 없음)
3. A의 오른쪽 노드 C 출력 → C의 왼쪽 노드 F 출력 → C의 오른쪽 G 출력
재귀적인 구조로 호출하고 먼저 현재 노드가 출력 된 후 왼쪽 노드가 있으면 왼쪽부터 없을 때 다시 돌아와 오른쪽 노드 출력

    

// 배열을 이용한 전위 순회(preoder traversal)

class BinaryTree {
    char[] arr;

    public BinaryTree() {}
    public BinaryTree(char[] data) {
        this.arr = data.clone();
    }

    public void preOder(int idx) {
        System.out.println("current : " + this.arr[idx]); // 먼저 현재 노드 출력 하고
        int left = 2 * idx + 1; // 왼쪽 노드 위치 
        int right = 2 * idx + 2; // 오른쪽 노드 위치 

        if (left < this.arr.length) {
            this.preOder(left); 
        }

        if (right < this.arr.length) {
            this.preOder(right);
        }
    }
}

public class TreeTraversalArrayTest {
    public static void main(String[] args) {
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);
        bt.preOder(0);

    }
}

    
  

    

// 연결리스트로 전위순회 구현하기 

class Node {
    char data;
    Node left;
    Node right;

    public Node(char data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeLinked {
    Node head;
    BinaryTreeLinked() {};
    BinaryTreeLinked(char[] arr) {
        Node[] nodes = new Node[arr.length];

        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
            }
            if (right < arr.length) {
                nodes[i].right = nodes[right];
            }
        }
        this.head = nodes[0];
    }

    public void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        this.preOrder(node.left);
        this.preOrder(node.right);
    }
}

public class TreeTraversalLinkedListTest {
    public static void main(String[] args) {
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTreeLinked bt = new BinaryTreeLinked(arr);
        bt.preOrder(bt.head);

    }
}


    
  

 

중위 순회(Inorder traversal)

순서 : 왼쪽 서브트리 → 부모 노드 → 오른쪽 서브트리 순서로 노드를 방문
경로 : H → D → I  → B → J  → E → A → F → C  → G

    

// 배열 중위 순회 구현하기 
    public void inOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.inOrder(left);
        }
        System.out.print(this.arr[idx] + " ");

        if (right < this.arr.length) {
            this.inOrder(right);
        }
    }
    
// 연결리스트 중위 순회 구현하기
	public void inOrder(Node node) {
        if (node == null) {
            return;
        }

        this.inOrder(node.left);
        System.out.print(node.data + " ");
        this.inOrder(node.right);
    }

    
  

 

후위 순회(poestorder traversal)

순서 : 왼쪽 서브트리  → 오른쪽 서브트리 → 부모 노드순서로 노드를 방문
경로 : H → I → D → J → E → B → F → G → C → A

    

// 배열 중위 순회 구현하기 
    public void postOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.postOrder(left);
        }

        if (right < this.arr.length) {
            this.postOrder(right);
        }

        System.out.print(this.arr[idx] + " ");
    }

    
// 연결리스트 중위 순회 구현하기
    public void postOrder(Node node) {
        if (node == null) {
            return;
        }
        if (node == null) {
            return;
        }

        this.postOrder(node.left);
        this.postOrder(node.right);
        System.out.print(node.data + " ");
    }


    
  

 

레벨 순회(levelorder traversal)

순서 : 루트 노드부터 한 레벨씩 내려가며 왼쪽부터 오른쪽으로 노드를 방문, 레벨별로 순차적으로 방문
경로 : A → B → C → D → E → F → G → H → I → J

    
// 배열 레벨 순회 구현
		public void levelOrder(int idx) {
        for (int i = 0; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }

// 연결리스트 레벨 순회 구현
		public void levelOrder(Node node) {
        Queue queue = new LinkedList<>();
        queue.add(node);

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

            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }


    
  

 

정리하면 부모 노드를 언제 방문하냐에 따라서 달라지며
부모의 서브트리, 그 서브트리의 서브트리를 먼저 해결하고
그 후 순서를 따른다고 이해하자.

전위 순회 : 부모 -> 왼쪽 -> 오른쪽
중위 순회 : 왼쪽 -> 부모 -> 오른쪽
후위 순회 : 왼쪽 -> 오른쪽 -> 부모 정리할 수 있겠다.