트리(Tree), 이진 트리(Binary Tree)

1. 트리(Tree)

1-1 트리란?

• 비선형 자료구조 중에서 자료간에 계층관계를 가진 계층형 자료구조(Hierachical Dta Structure)다

 

1-2 트리 주요 용어

 

출처: www.tutorialspoint.com

• 노드: 트리를 구성하는 원소
• 간선(edge): 노드를 연결 선
• 루트 노드(Root Node): 트리의 시작 노드
• 형제 노드(Sibling Node): 같은 부모노드의 자식노드들
• 서브 트리(subtree): 각 노드의 모든 자식노드
• 차수(degree): 한 노드가 가지는 서브 트리의 수
• 리프 노드(Leaf Node): 차수가 0인 노드
• 포리스트(forest): 여러 트리들의 집합

 

2. 이진 트리(Binary Tree)

2-1 이진트리란?

• 모든 노드의 차수가 2 이하인 트리

 

2-2 이진 트리의 분류

• 포화 이진 트리(Full Binary Tree)
  • 모든 레벨의 노드가 꽉 차서 포화 상태인 이진 트리

 

• 완전 이진 트리(Complete Binary Tree)
  • 노드의 위치가 포화 이진 트리의 노드 1번부터 n(노드의 갯수)번까지의 위치와 완전히 일치하는 이진 트리

 

• 편향 이진 트리(Skewed Binary Tree)
  • 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리

출처: Quora

 

2-3 이진 트리의 순회

• 순회(traversal)
  • 이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것
  • O(N)의 효율성
• 순회를 위해 수행하는 작업
  • D: 현재 노드 방문하여 데이터를 읽는 작업
  • L: 현재 노드의 왼쪽 서브 트리로 이동하는 작업
  • R:  현재 노드의 오른쪽 서브 트리로 이동하는 작업
• 전위 순회(Preorder Traversal)
  • DLR의 순서
• 중위 순회(Inorder Traversal)
  • LDR의 순서
• 후위 순회(Postorder Traversal)
  • LRD의 순서
• 이진 트리 순회 프로그램 구현

public class BinaryTreeMadyByLinkedList {
    public static void main(String[] args) {
        LinkedNode ln = new LinkedNode();
        TreeNode n7 = new TreeNode(null, "D", null);
        TreeNode n6 = new TreeNode(null, "C", null);
        TreeNode n5 = new TreeNode(null, "B", null);
        TreeNode n4 = new TreeNode(null, "A", null);
        TreeNode n3 = new TreeNode(n6, "/", n7);
        TreeNode n2 = new TreeNode(n4, "*", n5);
        TreeNode n1 = new TreeNode(n2, "-", n3);

        System.out.println("\nPreorder");
        ln.preorder(n1);

        System.out.println("\nInorder");
        ln.inorder(n1);

        System.out.println("\nPostorder");
        ln.postorder(n1);
    }
}

class TreeNode {
    TreeNode left;
    String data;
    TreeNode right;

    public TreeNode(TreeNode left, String data, TreeNode right) {
        this.left = left;
        this.data = data;
        this.right = right;
    }
}

class LinkedNode {
    private TreeNode root;

    public void preorder(TreeNode root) {
        if (root != null) {
            System.out.printf(root.data + " ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    public void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.printf(root.data + " ");
            inorder(root.right);
        }
    }

    public void postorder(TreeNode root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.printf(root.data + " ");
        }
    }
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음