[CS 스터디] Complete Binary Tree : 완전 이진트리

경·2022년 10월 1일

cs스터디

CS 스터디

목록 보기

2/3

완전 이진 트리

트리(Tree) 란?

트리를 그 모양이 뒤집어 놓은 나무와 같다고 해서 트리라는 이름이 붙었다.

트리의 특징

가상 최상위 노드인 루트와 자식 노드가 없는 단말노드, 루트와 단말노드를 제외한 내부노드로 구성되어있으며 노드와 노드 사이를 이어주는것을 엣지가 존재한다.
모든 노드는 서로 연결되어있다.
엣지를 하나 자르면 트리가 두개로 분리된다.
엣지의 수는 노드의 수 보다 1 작다.
하나의 노드는 반드시 하나의 부모만을 가져야하며 부모노드는 여러 자식 노드를 가질 수 있다.

이진 트리(Binary Tree)란?

이진트리는 기존의 트리에서 자식노드를 최대 두개만 가질 수 있게 구성한 트리이다.
이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있다.

완전 이진 트리(Complete Binary Tree)란?

완전 이진 트리는 앞서 설명한대로 이진트리의 한 종류이다.
이진트리와 동일하게 자식노드를 최대 두개만 가질 수 있다는 특징이 있지만 다른 이진트리들과는 다르게 왼쪽부터 차례로 입력된다는 큰 특징이 있다.

트리의 표현 방법

트리는 기본적으로 그래프 형태의 구조이다. 따라서 그래프의 인접 리스트 방식으로 표현할 수 있다.
완전 이진 트리의 경우 트리의 왼쪽부터채우기 때문에 배열로 표현할 수 있다.
- 루트 노드를 index 1로 표현하고, 좌측 자식을 2, 우측 자식을 2+1의 인덱스에 넣어서 저장한다.
별도의 class로 구성해 표현할 수 있다.

class 표현 예시

public class Tree {
    public void DFS(Node root){
        if(root==null) return;
        else {
            System.out.println(root.data+" ");   //전위순회
            DFS(root.leftNode);
            DFS(root.rightNode);    
        }
    }

    public static void main(String[] args) {
        Tree tr = new Tree();
        TreeClass tc = new TreeClass();

        Node n50 = tc.makeNode(50, null, null);
        Node n60 = tc.makeNode(60, null, null);
        Node n20 = tc.makeNode(20, n50, n60);
        Node n30 = tc.makeNode(30, null, null);
        Node n10 = tc.makeNode(10, n20, n30);
        /*
             10
           /    \
          20    30
         /  \  
        50  60
         */
        tr.DFS(n10);

    }
}

class Node {
    public int data;    //노드의 값
    public Node leftNode;    //왼쪽 자식노드의 값
    public Node rightNode;    //오른쪽 자식노드의 값

    public Node(int data, Node leftNode, Node rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }
}

class TreeClass {
    private Node newNode;    

    //데이터 지정
    public Node makeNode(int data, Node leftNode, Node rightNode) {
        newNode = new Node(data, leftNode, rightNode);

        return newNode;
    }
}