태그: Binary Search Tree

안녕하세요. 언제나 휴일입니다.

이번에는 이진 탐색 트리(Binary Search Tree)의 운행에 관한 소스 코드입니다.

이진 탐색 트리에서는 자료를 보관할 때 부모보다 작은 값을 갖는 자료는 부모의 왼쪽 서브 트리에 매달고 큰 값을 갖는 자료는 부모의 오른쪽 서브 트리에 매다는 이진 트리입니다. 그리고 이진 탐색 트리에서는 같은 값을 갖는 자료는 보관하지 않습니다. 이처럼 매달면 서브 트리도 이진 탐색 트리인 특징을 갖습니다.

binary search tree = { root, sub trees}

sub tree is binary search tree, left son’ s data <parent’s data > right son’s data,

MAX[N(sub tree)]=2

이진 탐색 트리
이진 탐색 트리

이진 탐색 트리의 모든 노드를 방문할 때도 재귀적인 방법으로 문제를 해결할 수 있습니다. 만약 루트를 먼저 방문한 후에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 방문하면 전위 순회(Pre Order Travel) 혹은 전위 운행이라고 말합니다.

위의 이진 탐색 트리에서 전위 순회하면 방문 순서는 50, 25, 15, 12, 40, 30, 43, 75, 60, 80, 77와 같습니다. 언제나 부모는 자식들보다 먼저 방문하고 있음을 알 수 있습니다.

PreOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

    doit(sr)

    PreOrderTravel (sr의 왼쪽 자식 노드, doit)

    PreOrderTravel (sr의 오른쪽 자식 노드, doit)

왼쪽 서브 트리를 방문한 후에 오른쪽 서브 트리를 방문한 후에 마지막으로 루트를 방문하는 것을 후위 순회(Post Order Travel)혹은 후위 운행이라고 말합니다.

위의 이진 탐색 트리에서 후위 순회하면 방문 순서는 12, 15, 30, 43, 40, 25, 60, 77, 80, 75, 50와 같습니다. 언제나 부모는 자식들보다 나중에 방문하고 있음을 알 수 있습니다.

PostOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

    PostOrderTravel (sr의 왼쪽 자식 노드, doit)

    PostOrderTravel(sr의 오른쪽 자식 노드, doit)

    doit(sr)

왼쪽 서브 트리를 방문한 후에 루트를 방문하고 오른쪽 서브 트리를 방문하는 것을 중위 순회(In Order Travel) 혹은 중위 운행이라고 말합니다.

위의 이진 탐색 트리에서 중위 순회하면 방문 순서는 12, 15, 25, 30, 40, 43, 50, 60, 75, 77, 80와 같습니다. 언제나 부모는 왼쪽 자식들보다 나중에 방문하고 오른쪽 자식들보다 먼저 방문함을 알 수 있습니다.

InOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

     InOrderTravel (sr의 왼쪽 자식 노드, doit)

    doit(sr)

     InOrderTravel (sr의 오른쪽 자식 노드, doit)

이진 트리의 운행

 

다음은 예제 코드의 실행 모습과 매달린 논리적 모습입니다.

이진 탐색 트리 운행
이진 탐색 트리 운행

이진탐색트리 매달린 모습

소스 코드