자료구조 알고리즘, 이진 트리 순회

 

Binary Tree

 

이진 트리의 특징

• i 번째 레벨의 최대 노드 수: 2^(i-1)
• 깊이가 k인 이진 트리의 최대 노드 수: 2^k-1

 

이진 트리 순회

 

Search == Traversal

• 어떠한 값이 주어어졌을 때 해당 값이 일치하는 노드가 있는지 보는 것
• 즉 모든 노드를 봐야 함

 

방법 (DFS / BFS)

•   DFS

• 트리의 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법
• Strack or Recursive를 이용한 구현

 

세가지 구현 방법

 

• Preorder Traversal (전위순회): 루트 > 왼쪽 > 오른쪽

void preorder ( nptr bt ) 
{
    if ( bt ) { // 현재 노드(bt)가 NULL이 아닌 경우에만 실행
		    print ( bt->data ); // 현재 노드의 데이터를 출력
        preorder ( bt->lchild ); // 왼쪽 자식 노드 순회
        preorder ( bt->rchild ); // 오른쪽 자식 노드 순회
    }
}

A B D H I E C F G

 

• Inorder Traversal (중위순회): 왼쪽 > 루트 > 오른쪽

void inorder ( nptr bt ) 
{
    if ( bt ) { // 현재 노드(bt)가 NULL이 아닌 경우에만 실행
        inorder ( bt->lchild ); // 왼쪽 자식 노드순회
        print ( bt->data ); // 현재 노드의 데이터를 출력
        inorder ( bt->rchild ); // 오른쪽 자식 노드 순회
    }
}

H D I B E A F C G

 

• Postorder Traversal (후위순회): 왼쪽 > 오른쪽 > 루트    

void postorder ( nptr bt ) 
{
    if ( bt ) { // 현재 노드(bt)가 NULL이 아닌 경우에만 실행
        postorder ( bt->lchild ); // 왼쪽 자식 노드 순회
        postorder ( bt->rchild ); // 오른쪽 자식 노드 순회
        print ( bt->data ); // 현재 노드의 데이터를 출력
    }
}

H I D E B F G C A

 

리스트를 이용하는 방법

 

      이진트리 (Binary Tree)

• 부모 노드의 인덱스를  i
• 왼쪽 자식 노드의 인덱스를 2*i +1
• 오른쪽 자식 노드의 인덱스는 2*i +2

 

BFS

• 트리의 레벨순으로 노드를 방문하는 방법
• 큐(Queue)를 이용해 구현

 

---

 

백준 1991

 

트리 순회 문제 

 

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력 1 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1 

ABDCEFG
DBAECFG
DBEGFCA

 

휴..

제발.. 풀 수 있게 해주세요..ㅠㅠ

 

 

입력받는 건.. 정말 잘 모르겠다.. 감이 안 잡힘ㅠ

휴ㅠㅠㅠㅠ

 

일단.. 공개처형 당하면 안되니까.. 

내일 코드카타 푸는 시간에 마저 풀어보기로.. 

내가 바보인걸까ㅠㅠㅠㅠ

 

어우 답답해ㅠㅠㅠ