트리 Tree 자료구조

Node와 Edge로 이루어진 자료구조이다.

정의 하자면 Cycle이 없는 그래프이다. 

 

배열과 구조체 2가지 방법으로 만들수 있다. 

배열로 만들게 되는 경우, 자식노드의 개수를 한정지어야 한다. 

구조체로 만들게 되는 경우

struct Node {
	Node child[]; 
    int value;
}

위와 같이 구성할 수 있다.

 

트리의 순회 방식은:

- 전위 순회: 각 부모 노드를 순차적으로 먼저 방문. (부모 -> 왼쪽 자식 -> 오른쪽 자식)

- 중위 순회: 왼쪽 하위 트리를 방문 후 부모 노드를 방문하는 방식. ( 왼쪽 자식 -> 부모 -> 오른쪽 자식)

- 후위 순회: 왼쪽 하위 트리부터 하위를 모두 방문 후 부모 노드를 방문하는 방식이다. ( 왼쪽 자식 -> 오른쪽 자식 -> 부모)

- 레벨 순회: 부모 노드부터 계층 별로 방문하는 방식이다.