이진 트리 (Binary Tree)와 순회

https://www.wikiwand.com/ko/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

 

트리의 구성 요소

노드

트리를 구성하고 있는 각각의 요소

 

간선(edge)

트리를 구성하기 위해 노드와 노드를 연결한 선

 

루트노드

트리 구조에서 최상위에 있는 노드

 

단말노드(Terminal node)

하위에 다른 노드가 연결돼 있지 않은 노드

 

비단말노드, 외부노드(Internal node)

단말 노드를 제외한 모든 노드, 루트노드 포함

 

Binary tree (이진트리)

루트를 중심으로 두개의 서브트리로 나눠지고 그 두개의 서브트리도 모두 이진트리여야 한다. -> 재귀적인 정의

 

Full binary tree (포화이진트리)

모든 level이 꽉 찬이진트리

 

Complete Binary tree (완전이진트리)

위에서 아래로, 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진 이진트리

 

순회 방식

전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

중위 순회

중위 순회(Inorder)은 다음의 순서로 진행된다.

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric)라고도 한다.

후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

https://www.wikiwand.com/ko/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)

 

문제 출처:https://www.acmicpc.net/problem/1991

1991번: 트리 순회

소스코드

트리 구조체를 만들어 그 안에 생성자와 소멸자를 만들고 search, insert, 전위, 중위, 후위 탐색을 하였다. 특히 메인에서 루트노드를 생성자로 NULL값 생성한 후 tmp 로 루트를 탐색하여 key값을 찾게되면 나중에 그 부분에 넣을 때 insert함수에서는 처음 루트값을 넣을때는 root->insert함수로 들어가서 실행해야 한다. 그리고 다음부터는 tmp가 루트를 기준으로 search를 하게 되므로 삽입시 이미 루트의 왼쪽 왼쪽 오른쪽 이렇게 위치가 지정이 돼 있어서 tmp->insert로 함수를 호출해서 노드를 넣어야 하며 그리고 insert함수에서 주의할 점은 노드 삽입 전에 생성자로 새로 노드를 생성자로 만들고 key값을 넣어야 한다는 것이다. 이렇게 두개를 동시에 하기 위해 애초에 생성자를 만들 때 입력 파라메타 값으로 char key 값을 주고 생성과 동시에 key값 삽입을 할 수 있게 구현하였다.