(C언어) 스레드 이진트리 [자료구조]
이번에는 스레드 이진 트리에 대해 공부해 보자. 보통 이진 트리를 순회할 때 순환 호출을 사용한다. 만약 이진 트리의 노드 개수가 많아지고 트리의 높이가 높아진다면 순환 호출은 상당히 비효율적이다. 그럼 순환 호출을 사용하지 않고 구현할 수 있는 다른 방법이 무엇일까? 먼저 위 이진 트리를 보자. 노드 개수 7개 (N) 총 링크의 개수(노드당 링크 2개) 14개 (2N) 다른 노드를 가리키는 링크의 수 6개 (N-1) NULL을 가리키는 링크의 수 8개 (N+1) 표와 같은 규칙을 가진다. NULL을 가리키는 링크는 N+1개나 존재하지만 사용하지 않는다. 스레드 이진 트리의 가장 큰 아이디어는 NULL을 가리키는 링크를 이용해 순환 호출 없이 트리의 노드들을 순회할 수 있도록 하는 것이다. NULL 링크..
2022.01.29