[자료구조] Tree 개념/정의

Tree

트리(Tree)는 하나 이상의 노드들로 구성된 유한집합이다. 트리는 가장 최상위에 존재하는 Root 노드와 그 노드서부터 내려가는 하위노드들의 구성으로 표현된다. 아래 그림을 보자

그림처럼 Tree를 표현하면 위 그림같이 될 것이다.
Root노드인 A는 하위 노드인 B,C,D노드가 있고 각각의 하위노드들은 또 자신들만의 하위노드들이 있다. 여기서 A에 대해 subTree는 B노드와 그의 하위 노드들과 C,D노드와 각각의 하위노드들이 될 것이다.

Tree 설계

그렇다면 Tree는 어떻게 설계하면 좋을까? 생각해보자 일단 노드 A는 data와 sub-Node를 저장할 Node변수 3개가 필요할 것이다. 그렇다면 아래 그림 처럼 Tree의 노드구조를 설명할 수 있겠다.

자 그럼 문제는 다음이다. 가령 root노드는 sub Node를 10개를 가지는데, 각각의 하위노드들은 1개의 하위 노드를 가진다면 메모리 낭비가 나타날 것이다. 이러한 공간 낭비를 방지하기 위해 설계된(?) Tree가 있으니 바로 아래에 설명할 이진트리이다.

이진 트리(Binary Tree)

이진 트리는 말 그대로 하위 노드를 2개를 가지는 Tree를 말한다. 이전 포스팅에서 설명했던 Doubly Linked List의 확장판(?) 이라고 생각하면 좋겠다.

이진트리 설계

Node의 구조는 아래 사진처럼 설계하면 된다.(이전 글의 DLL과 동일하다.)

이진트리의 Tree 구조는 전공수업에서 배웠을때, 단계를 걸쳐 설계되었다. 다음 그림을 확인해 보자

1단계: 형제(Sibling)Node끼리 같은 레벨에 존재시킨다.

2단계: 각노드의 아래는 왼쪽 하위 노드 오른쪽은 형제 노드는 오른쪽 하위 노드에 위치 시킨다.(위 그림에서 오른쪽으로 45도 기울인다고 생각하면 쉽다.)

위 단계를 거쳐 이진트리를 완성했다고 배웠다. 나중에 다른 교수님께 m원-B트리를 배우면서 원리를 까먹게 되었는데, 다시 공부하니까 이런 원리였다... 암튼 위처럼 이진 트리의 구조를 설명하였다.

트리 순회

위에 Tree에서 처럼 각각의 노드들을 탐색하여 data값을 가져오는 방법이 여럿있다. 트리 순회에는 중위순회(inOrder), 후위순회(postOrder), 전위순회(postOrder)가 있다. 간단하게 재귀메소드를 통해 작성할 수 있다.
아래코드를 확인해보자

//중위순회
private void inoder(Node temp)
{
    if(temp != null)
    {
        inoder(temp.left);
        System.out.print(temp.data+" ");
        inoder(temp.right);
    }
}

//후위순회
private void postoder(Node temp)
{
    if(temp != null)
    {
        postoder(temp.left);
        postoder(temp.right);
        System.out.print(temp.data+" ");
    }
}

//전위순회
private void preoder(Node temp)
{
    if(temp != null)
    {
        System.out.print(temp.data+" ");
        preoder(temp.left);
        preoder(temp.right);
    }
}

메소드의 private는 무시하자
순회구성을 모두 재귀메소드를 통해 구현하였다. 우선 중위 순회부터 보면, 왼쪽 노드의 inorder를 수행하고 자신의 data를 출력하고나서 오른쪽 노드의 inorder를 수행한다. 이를 재귀로 수행하는 것이다. 나머지 후위,전위도 비슷한 논리로 수행된다.

Tree를 통한 산술식 표현

Tree의 응용으로 산술식 표현이 있겠다. 나는 Tree개념에서 BST나 AVL B트리의 개념들이 더 중요하다고 생각해서 산술식표현의 코드리뷰는 하지 않겠지만, 코드는 github링크를 남겨놓겠다.

결론

이 트리의 개념은 BST나 AVL, B트리 같이 엄청나게 응용되어 설계된 Tree들의 근간이 되는 개념이다.
이후에 BST와 AVL, B트리에 대한 포스팅을 작성한 후에 Graph로 넘어갈까 한다.

---

이글은 이후에 BST, AVL, B-Tree 포스팅에 링크될 글이니까 너무 심각하게 안보셔도 됩니다. 그냥 제가 공부했던 내용들 정리차원에서 작성한거니까요~ 빠진내용도 많고 설명이 부족한 부분이 있으니, 틀린부분이나 혹시 질문있으면 댓글을 남겨주세요 ㅎㅎ

 

Tree_Github: github.com/JoSangYeon/Algorithm/tree/master/Tree

JoSangYeon/Algorithm

 

BST: jsy-coding-blog.tistory.com/23

[자료구조] BST - 이진탐색 트리(Binary Search Tree)