Binary Search Tree 활용 - Tree level 순회

<C언어로 쉽게 풀어쓴 자료구조 내용 > 인용

 

아래에서 작업한 이진 탐색 트리의 탐색,삽입,삭제의 기능의 내용을 그대로 가지고 와서 활용하도록 하자.

designatedroom87.tistory.com/15?category=869957

2. Binary Search Tree 만들기 - 삭제

 

Traversal 헤더 파일과 소스파일을 만들어서 트리의 레벨 순회 함수를 만들 것이다.

그리고 큐의 헤더 파일과 소스파일을 가지고 온다.

레벨 순회에는 자료 구조 중에서 큐가 필요하다.

designatedroom87.tistory.com/29?category=869063

Queue 만들기

 

1. 개념

레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법이다.

루트 노드의 레벨이 1이고, 아래로 내려갈수록 레벨은 증가한다.

동일한 레벨의 경우에는 좌에서 우로 방문한다.

지금까지의 순회법이 스택을 사용했던 것에 비해( 코드에는 스택이 나타나지는 않았지만 순환 호출을 하였기 때문에 간접적으로 스택을 사용한 것이다.) 레벨 순회는 큐를 사용하는 순회법이다.

[그림]

레벨 순회 코드는 큐에 하나라도 노드가 있으면 계속 반복하는 코드로 이루어져 있다.

먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로

한 번의 반복을 끝낸다.

이러한 반복을 큐에 더 이상의 노드가 없을 때까지 계속한다. 

위의 그림에서 보는 것처럼, 먼저 루트 노드인 +가 큐에 입력된 상태에서 순회가 시작된다.

큐에서 하나를 삭제하면, +가 나오게 되고, 노드 +를 방문한 다음,

노드 +의 자식 노드인 노드 * 와 노드 / 를 큐에 삽입한 다음,

다시 반복의 처음으로 되돌아 간다.

 

2. 트리 레벨 순회 알고리즘

트리레벨 순회 알고리즘 의사코드

알고리즘 설명

1. 큐를 초기화 한다.

2. 트리 root의 루트 노드를 큐에 삽입한다.

3. 큐가 공백 상태가 될 때까지 계속 다음을 반복한다.

4. 큐에서 맨 처음에 있는 노드를 pCur로 가져온다.

5. 만약 pCur가 NULL이 아니면

6. pCur의 데이터 값을 출력하고

7. pCur의 왼쪽 자식을 큐에 삽입한다.

8. pCur의 오른쪽 자식을 큐에 삽입한다. 

 

기존의 구현한 큐는 int형 데이터를 저장했으나, 여기서는 트리의 노드를 저장해야 한다.

 

3. 구현

기존에 만든 큐에서, 저장할 데이터 타입을 트리의 노드로 변경.

 

Traversal 소스 파일에 정의한 함수

 

메인 함수

 

프로그램 실행결과

 

위의 결과가 맞는지 안맞는지 알고 싶을 것이다.

그러면 확인을 해보자.

BSTInsert함수가 호출이 됬을 때, 노드들의 연결을 보자.

 

헤더 파일과 소스 파일

BinarySearchTree.c

0.00MB

BinarySearchTree.h

0.00MB

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB

Queue.c

0.00MB

Queue.h

0.00MB

Traversal.c

0.00MB

Traversal.h

0.00MB