트리(Tree)

1. 트리란?

노드와 엣지로 이루어진  자료구조이다.

• 사이클이 존재하지 않는다. 사이클이 존재한다면, 이는 그래프이다.
• 모든 노드는 자료형으로 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일하다.
• 노드가 N개라면 간선은 N-1개이다.
• 계층 구조가 확실한 구조에서 사용한다.

2. 트리 순회 방식

① 전위순회

부모-왼쪽 자식-오른쪽 자식 순으로 방문

void preOrder(int idx){
	if(tree[idx]){
    	cout<<tree[idx]<<' ';
        preOrder(idx*2);
        preOrder(idx*2+1);
    }
}

 

② 중위순회

왼쪽 자식-부모-오른쪽 자식 순으로 방문

void inOrder(int idx){
	if(tree[idx]){
        inOrder(idx*2);
        cout<<tree[idx]<<' ';
        inOrder(idx*2+1);
    }
}

 

③ 후위순회

왼쪽 자식-오른쪽 자식-부모 순으로 방문

void postOrder(int idx){
	if(tree[idx]){
        postOrder(idx*2);
        postOrder(idx*2+1);
        cout<<tree[idx]<<' ';
    }
}

이진트리로 디렉토리를 관리하고 있을 때 파일 탐색 시 사용하는 방식이다.

하위 디렉토리의 용량을 알고 있어야 하기 때문!

하위 서브트리 정보가 필요한 경우 후위순회를 사용한다.

 

④ 레벨순회

루트부터 레벨 순으로 방문(왼쪽-오른쪽)