자료 구조 | 연결리스트(3) 트리

연결 리스트에서는 각 요소가 다른 요소를 하나씩만 가리키고 있었다. 만약 가리키는 요소가 여러 개가 된다면 어떻게 될까. 학습 목표 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다. 연결 리스트와 트리 트리는 연결 리스트를 기반으로 한 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적이었다면, 트리에서는 2차원적으로 구성되어 있다. 각 노드는 일정한 층에 속하고 다음 층의 노드를 가리키는 포인터를 가진다. 트리가 시작되는 노드를 루트라고 한다. 루트는 다음 층의 노드를 가리키며 이를 자식 노드라고 한다. 이진 검색 트리에서 하나의 노드는 두 개의 자식 노드를 가진다. 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 크다. 이러한 트리 구조는 이진 검색을 수행하는데 유리하다. ..

2021.03.01