트리구조
-
[Data Structure] 연결 리스트 : 트리알고리즘 & 자료구조 2021. 1. 25. 14:15
트리는 연결리스트를 기반으로 한 새로운 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어있다고 볼 수 있다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다. 가장 높은 층에서 트리가 시작되는 노드를 '루트' 라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드' 라고 한다. 위의 그림을 살펴보자, 뭔가 규칙을 찾았는가? 왼쪽이 자식 노드는 자신의 값보다 작고 오른쪽 자식 노드는 자신의 값보다 크다. 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다. #include #include //이진 검색 트리의 노드 구조체 typedef struct node { //..