[자료 구조] Tree

트리(Tree) 구조란 무었인가?

링크드 리스트, 스택, 큐는 모두 직선형 구조를 가지고 있다. 직선형 자료 구조는 1차원적 구성 위주고 이는 곧 계층적, 계급적 구조를 표현하는데 한계를 가지고 있다. 우리가 이번에 다룰 트리(Tree) 자료 구조는 노드(Node)들과 가지(Branch)들로 이루어진 비선형 자료 구조이다. 트리(Tree)의 최상위에는 뿌리(Root), 즉 루트 노드가 위치하며 그 아래로 자식(Child) 노드들이 가지(Branch)들을 통해 연결된다. 맨 아래의 노드들은 보통 잎(Leaf), 리프 노드라 불린다. 루트(Root) 노드를 제외한 모든 노드(Node)들은 부모(Parent) 노드를 가지며, 잎(Leaf) 노드를 제외한 모든 노드들은 자식(Child) 노드를 가진다. 그리고 모든 노드들은 가지(Branch)들로 연결되있다. 아래 그림은 트리 구조와 각각 파트의 이름, 주요 용어들을 정리해놓은 그림이다.

트리(Tree) 컨셉과 주요 용어들

위의 그림에 나와있듯, 최상위에 위치한 노드는 뿌리(Root) 노드라 불리며, 가장 아래에 위치한 노드는 잎(Leaf)노드라 불린다. 그리고 트리(Tree)는 서브 트리(Sub Tree) 라 불리는 작은 트리들로 구성되있고, 서브 트리(Sub Tree) 들 또한 작은 트리들로 구성되있다. 위 그림 예제 같은 경우에는 왼쪽 서브 트리가 B 노드 부터 시작하고, 오른쪽 서브 트리는 C 노드 부터 시작한다. 그리고 B노드나 C 노드 둘다 아래로 서브 트리를 두지 않는다, 왜냐하면 D, E, F, G 노드들 모두 자식 노드가 없으니까~.

트리에서 조상(Ancestor) 관계와 후손(descendant) 관계란?

E 라는 노드가 T 노드의 조상(Ancestor)일 때, E 노드는 T 노드의 부모(Parent) 노드 이거나, T 노드의 부모(Parent) 노드의 조상(Ancestor)라 할 수 있다.
T 노드가 E 노드의 후손(Descendant)라 할 때, T 노드는 E 노드의 자식(Child) 노드 이거나, E 노드의 자식(Child) 노드의 후손(Descendant)라 할 수 있다.

노드(Node)의 깊이(Depth)란? 그리고 어떻게 계산되는가?

깊이란 루트(Root)노드에서 본인 위치까지에 있는 경로의 길이 이다. 노드 E 가 뿌리(Root) 노드라 할 때, 노드 E의 깊이(Depth)는 0이다. 루트(Root) 노드에서 한가지(Branch)씩 건너갈 때 마다 깊이는 +1 이 된다.

위의 그림을 예제로 들때

깊이 0 을 가진 노드는 : A
깊이 1 을 가진 노드는 : B, C
깊이 2 을 가진 노드는 : D, E, F, G

가 된다.

전체의 깊이(Depth Of Tree)란 최 하위에 위치한 잎(Leaf) 노드의 깊이(Depth)를 말한다. 위 그림의 경우에 Depth Of Tree는 2 가 된다.

트리 순회(Traversal)란? 그 종류, "Preorder"(전위), "Postorder"(후위), "Inorder"(중위) 순회는 어떻게 실행되는가?

• 전위 순회(Preorder traversal)

• 전위 순회(Preorder traversal)은 부모(Parent) 노드에서 자식(Child)노드로 진행된다
1. 첫번째로 루트 노드를 방문한 후, 루트노드의 왼쪽 자식 노드로 이어간다
2. 왼쪽 서브 트리를 전위 순회방식으로 순회한다.
3. 그 후 오른쪽 서브 트리를 전위 순회방식으로 순회한다.
• 위의 그림 예제에 나와있는 트리를 전위 순회 방식으로 순회하면
• ABDECFG 와 같다.

• 후위 순회(Postorder traversal)

• 후위 순회(Postorder traversal)은 자식(Child) 노드에서 부모(Parent)노드로 진행된다
1. 가장 왼쪽 아래에 위치한 자식노드를 방문한다, 그리고 그 자식 노드의 형제 노드를 방문한 후, 부모 노드로 진행한다.
2. 왼쪽 서브 트리의 최 상위 노드에 도달할 때 까지 후위 순회를 진행한다
3. 그 후, 오른쪽 서브 트리에서 후위순회를 진행한다.
4. 마지막으로 루트 노드를 방문함으로써 후위순회를 마친다.
• 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
• DEBFGCA 와 같다

• 중위 순회(Inorder traversal)

• 중위 순회(Inorder traversal)은 가장 아래 왼쪽 자식 노드에서 시작해 부모 노드를 거친 후에 오른쪽 자식 노드(시작 노드의 형제 노드)로 이어간다
1. 가장 왼쪽 잎(leaf) 노드를 방문한다, 그리고 그 부모 노드를 방문 후, 아래로 형제 노드를 방문한다
2. 이러한 방식으로 루트 노드까지 중위 순회를 이어간다.
3. 그리고 오른쪽 서브 트리를 중위 순회로 순회한다
• 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
• DBEAFCG 와 같다