아래 그림의 이진 트리를 이용하여 트리 운행 과정과 결과를 나타내시오.(전위순회, 중위순회, 후위순회) [자료구조]

소개글

A+ 받은 레포트입니다.
이진 트리를 이용하여 트리 운행 과정과 결과를 나타내고, 문제를 풀기위해 수행한 자료조사 등의 추가 내용들도 정리하였습니다.

목차

I. 트리 운행과정과 결과
1. 전위순회
2. 중위순회
3. 후위순회

II. 문제를 풀기위해 수행한 자료조사 등의 추가 내용
1. 이진트리의 정의
2. 이진 트리의 순회
1) 이진 트리의 순회 방법
(1) 전위 순회
(2) 중위 순회
(3) 후위 순회

III. 참고문헌

본문내용

1.이진트리의 정의
트리 중에서 가장 많이 쓰이는 트리가 이진 트리이다. 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다. 서브 트리는 공집합일 수 있다. 따라서 이진 트리의노드에는 최대 2개까지의 자식노드가 존재할 수 있고 모든 노드의 차수는 2 이하가 된다. 또한 이진 트리에는 서브 트리간의 순서가 존재한다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별된다.
이진 트리의 정의는 다음과 같다. 공집합이거나, 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리여야 한다.

2.이진트리의 순회
이진 트리는 데이터를 저장하기 위한 자료 구조이다. 데이터는 노드의 데이터 필드를 이용하여 저장된다. 이진 트리를 순회(traversal)한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다. 트리를 사용하는 목적은 트리의노드에 자료를 저장하고 필요에 다라서 이 자료를 처리하기 위함이다. 따라서 트리가 가지고 있는 자료를 순차적으로 순회하는 것은 이진 트리에서 중요한 연산이다.

1)이진 트리의 순회 방법
이진 트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있다. 이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 만약 루트를 방문하는 작업을 N 이라고 하고 왼쪽 서브 트리 방문을 L, 오른쪽 서브 트리 방문을 R이라고 하면 다음과 같이 3가지 방법을 생각할 수 있다. 즉 루트를 서브 트르에 앞서서 먼저 방문하면 전위 순회, 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회, 루트를 왼쪽과 오른쪽 서브 트리 방문 후에 방문하면 후위 순회가 된다.

참고 자료

C언어로 쉽게 풀어쓴 자료구조 | 천인국 외 | 생능출판사 | 2017
YouTube ‘이진트리 탐색 운행법’. https://youtu.be/6WTHpidiFjc