자료구조 9일차 : 트리

오늘은 선형구조를 마치고 비선형 자료구조인 트리에 대해서 알아보겠습니다.

 

비선형자료구조는 앞서 알아보았던 선형 자료구조와 달리 규칙이 없는 것이 특징입니다.

 

 

트리의 모양과 각 노드들의 역할입니다.

트리의 구조가 모두 위와 같은 것은 아니며 트리의 형태를 예시로 든 것입니다.

맨 위에 위치한 노드를 루트노드라고 부르며 레벨 0 이러고도 부릅니다.

그 아래로 루트 노드와 연결되어 있는 노드 B, C를 레벨 1 이라고 부릅니다. 

노드 B, C를 노드 A의 자식노드라고 부르며  노드 A는 노드 B, C의 부모 노드라고 부릅니다.

같은 방식으로 노드 D, E, F는 레벨 2 이며 노드 G, H, I는 레벨 3입니다.

같은 줄에 있는, 즉, 같은 레벨인 노드들은 형제노드라고 부릅니다.

 

트리는 여러갈래로 뻗어져있는 모양은 본떠서 포레스트 구조라고도 불립니다.

 

 

다음은 이진트리에 대해서 알아보겠습니다.

이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 

이진트리의 큰 갈래입니다.

 

최소 노드를 가지는 이진트리와 최대 노드를 가지는 이진 트리를 비교한 그림입니다.

 

 

트리 구조는 양 갈래로 뻗어지는 구조이기 때문에 데크 큐와 같이 양 쪽에 포인터를 가지고 있습니다.

 

 

왼쪽 편향 이진 트리의 경우에 포인터가 연결되는 방식입니다.

 

트리의 노드를 선언할 떄에는 왼쪽 포인터 변수와 오른쪽 포인터 변수를 같이 선언해줍니다.

 

 

다음은 이진트리 순회에 대해서 알아보겠습니다. 

이진트리에서 데이터들을 탐색할 때 사용하는 방법입니다.

이진트리에서 순회를 할 때 사용하는 개념은 세가지가 있습니다.

그 작업들은 위와 같습니다.

 

 

순회의 종류들입니다. 

오늘은 전위 순회에 대해서 알아보겠습니다.

전위순회는 D->L->R 순으로 진행되겠습니다.

 

 

전위순회를 실행할 시에 노드 탐색 순서입니다.

 

 

위의 그림의 구조를 글로 설명한 예시입니다.

위의 글을 읽어보시면서 이해를 해보시면 도움이 되실겁니다.