트리

트리

:사이클이 없는 그래프

정점의 개수   :v 

간선의 개수: v-1

루트 있는 트리

루트 있는 트리

1번이 루트다 → 부모가 없음

1은 2의 부모 ,2는 1의 자식

2는 4의 부모 ,4는 2의 자식

3의 자식 6,7

4,5,6,7 →단말 정점 

깊이: 루트에서부터 거리 (ex)루트 1의 깊이를 0이라 하면 4의 깊이는 2)

 

이진 트리:

자식을 최대 2개만 가지고 있는 트리

'트리의 표현: 배열 a[i][0]:i의 왼쪽 노드 ,a[i][1]:i의 오른쪽 노드 로 구현 가능

 

트리의 순회(이진 트리)

1.프리오더   -전위 순회  

-노드 방문

-왼족 자식 노드를 루트로 하는 서브트리 프리오더

-오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더

2.인오더 -중위 순회

-왼족 자식 노드를 루트로 하는 서브트리 인오더

-노드 방문

-오른쪽 자식 노드를 루트로 하는 서브 트리 인오더

3,포스트오더 -후위 순회

-왼족 자식 노드를 루트로 하는 서브트리 포스트오더

-오른쪽 자식 노드를 루트로 하는 서브 트리 포스트오더

-노드 방문