원본 링크

트리 자료구조

각각을 노드 (Node)라고 하며,

최상위 노드를 Parent노드

노드 간의 연결하는 선은 간선(Edge)라고 한다.

노드 간에는 부모-자식 관계가 존재하며

같은 계층의 노드는 형제 노드라고 한다.

더이상 자식 노드가 없는 노드 (트리의 맨 하단)를 리프(Leaf Node) 노드라고 합니다.

서브 트리는 트리 내에 또 다른 트리형태가 있는 것을 이야기함

각 노드에서 뻗어나온 간선의 개수를 노드의 차수(degree)라고 합니다.

루트로부터 시작해서 특정 노드에 도착하기위해서 거쳐야만 하는 간선의 수를 depth 라고 한다.

트리의 정의

한개 이상의 노드로 이루어진, 사이클이 없는, 연결 그래프

트리가 될 수 없는경우 (사이클)

트리가 될 수 없는경우 (연결 그래프가 아님)

이진 트리 (Binary Tree)

트리는 자식을 무한개로 가질수 있지만 이진트리는 자식을 두개밖에 가질 수 없다.

이진 트리의 길이는 최대 N, 최소 log(N+1)이 될수 있다.

balanced 이진 트리가 한쪽으로 치우쳐진 이진 트리 보다 디비에서 결과를 찾기위해서 좋다.

완전 이진 트리는 맨 마지막의 레벨의 노드를 제외한 나머지 노드는 완전히 채워져있으며(자식이 2개) 마지막 레벨의 노드는 가능한 가장 왼쪽에 있어야합니다.

포화 이진트리는 모든 노드가 자식이 2개인 트리를 말한다.

이진 트리 순회 방식

전위, 중위, 후위는 부모를 언제 방문하냐를 기준으로 나눈다.

전위: 부모를 1순위로 방문

중위: 부모를 2순위로 방문

후위: 부모를 3순위로 방문

레벨: 레벨순서대로 방문

후위 순회를 통해서 폴더의 용량을 알수 있다.

상위 폴더의 용량을 알려면 그 폴더 하위에 있는 모든 용량을 알아야하므로 이때 후위 순위가 쓰인다.