[자료구조] 트리와 이진트리

트리란? 

1. 그래프의 한 종류이다. 
2. 트리는 노드로 이루어진 자료 구조이며 다음과 같은 특성을 가지고 있다. 
3. 트리는 하나의 루트 노드를 갖는다.
4. 루트 노드는 0개 이상의 자식 노드를 가지고 있으며 그 자식들도 모두 마찬가지이다.
5. 노드들과 노드들을 연결하는 엣지들로 구성되어 있으며 이 연결된 엣지들은 절대로 사이클이 존재하지 않는다. 
6. 사이클이 존재하지 않기 때문에 간선수는 무조건 노드의 수 - 1 을 만족한다.
7. 루트 노드를 제외한 모든 노드들은 단 하나의 부모노드를 가진다.
8. 루트에서 어떤 노드로 가는 경로는 Unique하다.

 

트리와 관련된 용어

1. depth : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 엣지의 수를 말한다.
2. height : 루트노드에서 잎새노드에 이르는 가장 긴 경로의 엣지 수를 의미한다.
3. Level : 이때 특정 높이를 가지는 노드들의 집합을 Level이라고 부른다. 
4. Leaf node : 여기서 Leaf node는 자식노드가 없는 최하단의 노드들을 의미한다. 
5. internal node : Leaf node가 아닌 노드들을 말한다.
6. degree : 각 노드가 지닌 가지의 수를 말한다.
7. degree of tree : 트리의 최대 차수를 말한다.

 

이진트리란? 

자식노드가 최대 두 개인 노드들로 구성된 트리를 말한다. 
이진트리는 full binary tree, complete binary tree, perfect binary tree 등이 있다. 

full binary tree 

모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리

complete binary tree

마지막 Level을 제외한 모든 Level에 위치한 노드들이 꽉 채워진 이진트리이다. 

무조건 데이터는 왼쪽에서 오른쪽으로 채워져야 한다.

Perfect binary tree 

full binary tree이면서 완전 이진 트리인 경우를 말한다.  즉, 모든 노드들이 두개의 자식 노드를 가지며 모든 Leaf Node가 동일한 Level을 가지고 있어야 한다. 각 높이 h마다 노드의 개수가 정확히 2^(h-1) 이여야 한다. 

그래프 vs 트리 

1. 트리는 그래프의 한 종류이기도 하다. 그렇다면 일반적인 그래프와 차이점이 무엇일까? 
2. 우선 트리는 그래프와 다르게 무방향인 경우가 존재하지 않다. 다음으로 가장 중요한 차이점은 트리는 사이클이 불가능하며, 자체 간선도 불가능하고 이를 정리하자면 비순환 그래프의 특징을 가지고 있다. 
3. 그래프는 루트 노드라는 개념이 존재하지 않지만, 트리는 루트 노드를 꼭 가지고 있어야만 한다. 
4. 트리는 그래프와 다르게 부모-자식 개념도 존재한다. 

 

트리 순회

트리순회란 트리의 모든 노드를 특정 방법으로 방문하는 과정을 말한다. 트리 순회에는 부모, 자식노드들을 방문하는 순서에 따라 전위순회, 중위순회, 후위순회 3가지로 분류된다. 

preorder (전위순회) 

노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문하는 방식 

    void preorder(TreeNode currentNode) {
        if(currentNode != null) {
            System.out.print(currentNode.data);
            inorder(currentNode.left);
            inorder(currentNode.right);
        }
    }

inorder (중위순회)

왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 방문하는 방식   

    void inorder(TreeNode currentNode) {
        if(currentNode != null) {
            inorder(currentNode.left);
            System.out.print(currentNode.data);
            inorder(currentNode.right);
        }
    }

postorder (후위순회) 

왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 방문하는 방식 

    void postorder(TreeNode currentNode) {
        if(currentNode != null) {
            inorder(currentNode.left);
            inorder(currentNode.right);
            System.out.print(currentNode.data);
        }
    }

 

 

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

트리(tree)와 이진트리(binary tree) · ratsgo's blog

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog