트리의 구현과 순회는 뭘까?

 

21.1 도입

• 계층적 구조의 자료 구조

상위-하위 개념으로 연결된 트리 구조

특별한 규칙을 가진 트리 구조

 

• 연결된 두 노드 중 상위에 있는 것이 부모 노드 , 하위는 자식 노드
• 부모 노드가 같은 두 노드는 형제 노드
• 부모 노드와 그의 부모들을 통틀어 선조 노드
• 자식 노드와 그의 자식들을 통틀어 자손 노드
• 모든 노드의 선조이고, 부모이면 뿌리 노드 , 루트(root)
• 자식이 하나도 없는 노드는 잎 노드 , 리프(leaf)

트리와 노드 속성

• 깊이 : 루트에서 어떤 노드까지 도달하기 위해 거쳐야하는 간선의 수
• 높이 : 트리에서 가장 깊숙히 있는 노드의 깊이

트리의 재귀적 속성

• 가장 유용하게 쓰이는 이유는 재귀적 속성때문이다.
• [상위-하위 개념으로 연결된 트리 구조] 에서 ‘탐색형 자료구조(=t)’에서 그 자손들로 구성된 트리를 ‘t’를 루트로 하는 서브트리 라고 한다.
• 모든 트리는 루트와 루트 밑에 있는 서브 트리라고 얘기할 수 있다.

트리의 표현

• 각 노드를 하나의 구조체나 객체로 표현하고, 이들을 서로의 포인터로 연결하는 것
• 각 노드들은 자신의 부모와 모든 자손들에 대한 포인터를 가지고 있다.

21.2 트리의 순회

• 자료를 전부 순회하는 것에서 트리의 재귀적 속성을 이용한다.
• 트리가 루트가 주어질 때 루트를 방문하여 각 서브트리로 재귀적으로 방문하는 함수를 만들어 트리의 모든 노드를 순회할 수 있다.
• O(n)시간 걸린다.

ref

• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략