DataStructure - 이진트리

이진트리

순회 방법의 선택

- 순서는 중요치 않고 노드를 전부 방문하기만 하면 된다면 전위, 중위, 후위 순회 중 어떤 것이든지 관계없다. 예를 들어, 트리의 모든 노드 값을 순서  와 상관없이 출력하기만 한다면 순회 방법은 중요하지 않다.

- 자식 노드를 처리한 다음에 부모 노드를 처리해야 하는 문제라면 당연히 후위순회를 사용하여야 한다. 왜냐하면 하위 디렉터리의 용량이 계산되어야 만이 현재의 디렉터리 용량을 계산할 수 있기 때문이다.

- 부모 노드를 처리한 다음에 자식 노드를 처리해야 한다면 전위 순회를 사용하여야 한다. 예를 들어, 모든 노드의 레벨을 계산하기 위해서는 전위 순회를 사용해야 한다. 루트 노드의 레벨이 1이고 어떤 노드의 레벨은 부모 노드의 레벨보다 1이 크기 때문이다.

스레드 이진트리

이진트리의 노드에는 많은 NULL 링크들이 존재한다. 만약 노드의 개수가 n이면 각 노드당 2개의 링크가 연결되어 있으므로 전체 링크의 수는 2n이다. 이들 중 루트를 제외한 n-1개의 노드가 부모와 연결되었다. 따라서 2n개 중에서 n-1을 제외한 나머지 n+1개의 링크가 항상 NULL 이다. 따라서 이들을 잘 활용하면 순환 호출 없이도 트리의 노드들을 순회할 수 있다. 이런 트리를 스레드 이진트리(threaded binary tree)라 한다.

중위 순회를 위한 스레드 이진트리에서 중위 순회로 방문할 때 어떤 노드 바로 앞에 방문되는 노드를 중위 선행자(inorder predecessor)라 하고 다음에 방문하는 노드를 중위 후속자(inorder successor)라 한다. 스레드 이진트리에서는 NULL 링크를 재사용한다. 링크 값이 NULL을 갖는 대신에 중위 선행자나 중위 후속자를 저장시켜 놓는 것이 스레드 이진트리의 핵심 아이디어읻. 이것은 스레드(thread), 즉 실을 이용하여 노드들을 순회 순서대로 연결시켜 놓는다는 의미이다.

---