3. 이진 트리의 연산 ( 노드의 개수, 단말 노드의 개수, 트리의 높이 구하기 )

1. 이진 트리의 노드의 갯수 구하기

이진 트리 안의 노드의 갯수를 세어서 표시한다.

노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다.

각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 된다.

이진 트리에서 노드의 갯수 구하는 알고리즘 의사코드

2. 단말 노드 갯수 구하기

단말 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다.

순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 NULL이 되면, 단말 노드이므로 1을 반환한다.

만약 그렇지 않다면 비단말 노드이므로 각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다.

이진 트리에서 단말 노드의 갯수 구하는 알고리즘 의사코드

3. 트리의 높이 구하기

마찬가지로 먼저 각 서브 트리에 대하여 순환호출을 하여야 한다.

순환 호출이 끝나면 각 각 서브 트리로부터 서브 트리의 높이가 반환되어 왔을 것이다.

서브 트리들의 반환값 중에서 최대 값을 구하여 반환 하여야 한다.

아래의 [그림 1]을 먼저 보자.

아래의 M은 함수를 의미하는데, 둘 중에 큰 값을 리턴하는 함수이다.

[ 그림 1]

아래는 이진 트리에서 트리의 높이 구하는 알고리즘 수도 코드

프로그래밍은 앞에서 BinaryTree헤더 파일과 소스 파일에 위의 함수들을 정의하고 구현합니다.

 

1. 이진 트리에 연결된 모든 노드들을 구하는 함수

 

2. 이진 트리에 연결된 모든 단말노드들을 구하는 함수

3. 이진 트리의 높이를 구하는 함수

main 함수

 

위 main함수에서 연결한 트리는 아래 그림은 아래와 같다.

위의 그림을 보면서 아래의 프로그램 결과를 보도록 하자.

 

아래는 모든 헤더 및 소스 파일

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB