이번 포스트는 트리라는 자료구조를 다뤄볼 것이다. 앞서 다뤄봤던 배열, 리스트, 스택, 큐와는 이질적인 자료구조인데 이는 트리를 설명하면서 뒤에서 다뤄보도록 하겠다.

트리

트리(Tree)란?

• 계층적 관계를 표현하는 자료구조 (고급 자료구조)

가지를 늘려가며 뻗어나가는 자료구조이다. 이 자료구조는 데이터를 추가하거나 삭제하는 거에 초점이 되어있지 않고, 무엇인가를 표현해야하는 모습의 형태를 띈 자료구조이다. 그리고 이러한 자료구조는 흔하게 접할 수 있다. 컴퓨터 디렉터리 구조, 집안의 족보와 같은 부분이 이에 해당한다. 그러면 트리에 관련 용어를 다음 사진과 함께 보도록 하겠다.

• 노드(Node)
  그림에서 A부터 I 사이에 있는 모든 요소를 노드라고 표현할 수 있음.
• 간선(Edge)
  노드와 노드 사이에 있는 연결선
• 루트노드(Root Node)
  트리의 자료구조에서 최상위 자리에 있는 노드, 사진에서는 A가 제일 위에 있기에 A가 루트노드라고 표현할 수 있음.
• 단말노드(Terminal Node)
  아래 노드가 연결이 안된 노드, 사진에서는 H,I,E,F,G 가 단말 노드라고 할 수 있다. 끝에 있기에 잎사귀 노드라고도 불린다.
• 내부 노드(Internal Node)
  단말 노드를 제외한 모든 노드. 비단말 노드라고도 부른다.
• 레벨(Level)
  트리에서 각 층별로 숫자를 매길 때, 이를 숫자로 표현한다. 사진에서는 A노드는 레벨 0, H,I는 레벨 3으로 표현할 수 있다.
• 높이(Height)
  트리의 최고레벨

---

이진 트리 (Binary Tree)

트리는 큰 트리 속에 작은 트리가 계속 반복되어 들어가 있는 재귀적인 형태를 띄는 자료구조이다. 그렇기에 이를 구현하는 코드를 작성할 때에도 재귀를 많이 사용한다. 트리 속에 있는 작은 트리, 우리는 이 트리를 서브 트리(Sub Tree)라고 지칭한다.

이진트리(Binary Tree)란?

• 루트 노드를 중심으로 2개의 서브트리로 구성되어 있는 트리
• 나눠진 두 서브 트리도 모두 이진 트리여야함.

만약, 노드가 위치해야할 곳에 노드가 없다. 이도 이진 트리에 속한다고 할 수 있을까?
정답은 O다. 그 이유는 공집한(empty set)도 노드가 존재하는 것으로 간주하기 때문이다. 이렇게 이진트리는 트리 구조에서 큰 범위로 사용되는 용어라고 할 수 있다. 그러면 조금 더 자세하게 이진트리의 종류를 알아보도록 하겠다.

포화 이진 트리(Full Binary Tree)

설명에 앞서 사진부터 첨부하였다. 위 사진은 이진 트리중에서도 모든 레벨이 꽉 찬 이진 트리이다. 위 트리는 이진트리이면서도 모든 레벨에 필요한 노드들이 다 들어가있기에 우리는 이를 포화 이진 트리(Full Binary Tree)라고 한다. 포화의 정의가 꽉 차 있다는 뜻이 내포되어 있기에 이를 생각하면 이해가 더 잘 될 것이다.

완전 이진 트리(Complete Binary Tree)

사실, 이 트리는 제일 위 사진이랑 유사하다. 하지만, 위 사진에 있는 트리를 우리는 완전 이진 트리 라고 한다. 모든 레벨이 꽉 차 있는 포화 이진 트리와 다르게 완전 이진 트리는 다 레벨이 차 있지는 않지만, 단말 노드까지 오기 전에 빈틈없이 노드가 채워져 있다는 것을 사진을 보면 알 수 있다. 이렇게, 레벨을 다 채우지는 않았지만 쉽게 말해 공집합 노드가 없는 트리를 우리는 완전 이진 트리(Complete Binary Tree)라고 한다.

---

이진 트리 자료구조의 ADT

다음은 이진 트리 자료구조의 ADT이다. 트리 자료구조의 ADT는 앞서 다룬 자료구조의 ADT와 다르게 데이터의 추가/ 삭제에만 치중되어 있지 않고 트리의 모습을 표현하려는 자료구조라는 것을 감안하면 될 것이다.

• 이진 트리노드를 생성하여 그 주소값을 반환

    BTreeNode * MakeBTreeNode(void);

• 노드에 저장된 데이터를 반환

  	BTData GetData(BTreeNode * bt);

• 노드에 데이터를 작성한다. data로 전달된 값을 저장

  	void SetData(BTreeNode * bt, BTData data);

• 왼쪽/오른쪽 서브 트리의 주소값을 반환

  	BTreeNode * GetLeftSubTree(BTreeNode * bt);

  BTreeNode GetRightSubTree(BTreeNode bt);
  

• 왼쪽/오른쪽 서브 트리 연결
  (만약, 이미 서브트리가 존재하면 해당 트리 삭제 후 새로운 서브 트리를 연결)

  void MakeLeftSubTree(BTreeNode * main, BTreeNode sub);
  void MakeRightSUbTree(BTreeNode * main, BTreeNode sub);

---

이진 트리의 순회 (Traversal)

위 ADT에서 마지막 함수 선언에는 조건이 있는 것을 확인할 수 있었다. 이미 서브트리가 존재하는 트리에 그 트리를 삭제하고 새로운 서브 트리를 연결하려고 할 때는 기존에 있던 트리를 삭제해줘야한다. 만약, 그 트리를 동적할당으로 구현했고, 그 트리도 노드가 한 개가 아니라 그 트리를 루트 노드로 밑에 더 서브트리를 가지고 있는 트리라면 하나씩 참조하면서 데이터의 메모리를 free해줘야 한다. 이렇게 트리를 순회해서 데이터를 참조해야하는 경우가 생기기에 우리는 순회 방법을 알아야한다.

사실, 크게 위 사진에 있는 3가지 순회밖에 존재하지 않는다.

• 전위 순회
  : 루트 노드를 먼저 순회한 이후, 서브트리중에서 왼쪽에서 오른쪽으로 참조한다.

• 중위 순회
  : 큰 트리 기준으로 왼쪽 서브트리 중 단말노드부터 시작해 올라오면서 루트 노드를 중간에 참조한 후 마지막 오른쪽 서브트리를 참조한다.

• 후위 순회
  : 왼쪽 서브트리 단말노드에서 오른쪽 서브트리를 참조한 이후, 맨 마지막에 루트 노드를 참조한다.

위 순회 방법은 재귀적 방법으로 구현이 가능하다. 또한, 이 재귀적 구현을 하기 위해서는 재귀의 탈출 조건이 필요한데, 재귀는 서브트리가 NULL일 때를 탈출 조건으로 해서 구현하면 된다.