자료구조/수업

18. 트리의 운행(9-2)

멜데스 2017. 6. 14. 18:04



1. 트리의 운행(tree traversal) 

 트리의 운행(tree traversal) 이란? 

 트리 구조의 각 노드를 전부 한번씩 방문하여 검색해내는 방법 

 일반 트리의 운행법 

 레벨 순서 (level order) 운행 방법 

 가장 간단한 트리 운행법으로 트리의 각 노드를 근 노드부터 시작하여 레벨순서대로 노드를 차례로 방문하여 검색하는 방법 

 하향식 레벨 순서(topdown level order) 방법 

- 트리의 근 노드로 부터 시작하여  점차 레벨이 낮은 부분의 노드들을 순서대로 검색해 나가는 방법 

 상향식 레벨 순서(bottom up level order) 방법 

- 트리 구조의 가장 낮은 레벨에 있는 잎 노드부터 시작하여 점차 상위  

레벨의 노드를 순서대로 검색하고 마지막으로 근 노드를 검색하는 운행 방법 



 노드의 위치에 따른 운행법 

 전위 운행법(preorder traverse) : root-left-right 운행법 

 근 노드를 방문하고, 그 다음 레벨의 서브트리를 차례로 방문해서 검색하는 방법 

 만약 서브트리를 운행하던 중 잎 노드를 만나면 오른쪽에 있는 형제노드를 방문하여 검색하게 된다.  

 즉 근 노드의 왼쪽  서브트리를 먼저 검색하고 난 후 오른쪽 서브 트리를 검색하게 된다. 

 이때 서브트리의 운행은 근 노드를 기준으로 할 때와 같다. 


 후위 운행법(postorder traverse ) : left-right-root 운행법 

 후위 운행법은 먼저 서브트리를 방문 처리한 후 근 노드를 마지막으로 운행하는 방법 

 이때 한 서브트리의 처리가 끝나면 형제노드의 서브트리로 넘어간다. 


 후위 운행 순서 : E→F→B→K→L→M→G→C→H→I→J→D→A 


 패밀리 순서(family order)운행법 : 스택 이용 방법 

 먼저 근 노드를 검사하고, 그 다음 근 노드의 자식 노드들을 차례대로 

검사한 후 가장 늦게 검사된 자식 노드로부터 역순으로 앞의 작업들을  

순환적으로 반복하여 운행하는 방법 


 방문 순서 과정 

근 노드를 방문한다. 

근 노드의 자식 노드를 차례대로 방문하여 스택에 저장한다. 

더 이상 자식 노드가 없으면, 스택의 TOP에서 1개의 노드를  

출력하여 출력된 노드의 자식 노드를 스택에 입력하고,  

스택에 더 이상의  데이터가 없을 때까지 위 과정을 반복한다.  

단, 출력된 노드의 자식노드가 존재하지 않으면 스택의  

마지막 노드를 출력한 후 위 과정을 반복한다. 




 이진 트리의 운행법(binary tree traversal) 

 왼쪽 서브트리가 오른쪽 서브트리보다 우선하는 경우 

 근 노드→ 왼쪽 서브트리→ 오른쪽 서브트리 

 왼쪽 서브트리→근 노드→ 오른쪽 서브트리 

 왼쪽 서브트리→ 오른쪽 서브트리→근 노드 

 

 오른쪽 서브트리가 왼쪽 서브트리보다 우선하는 경우 

 근 노드→ 오른쪽 서브트리→ 왼쪽 서브트리 

 오른쪽 서브트리→근 노드→ 왼쪽 서브트리 

 오른쪽 서브트리→ 왼쪽 서브트리→근 노드 



 이진트리의 노드 정의 

 struct node { 

     struct node *leftnode; 

     char data; 

     struct node *rightnode; 

}; 

 

 전위 운행법(root-left-right)의 알고리즘(polish 표기법) 

 이진 트리의 근 노드에서 출발하여 먼저 근 노드를 출력한 후 왼쪽  

서브 트리로 이동하여 왼쪽 서브 트리의 근 노드를 출력한다.  

이와 같이 왼쪽 서브 트리로 이동과 출력을 마지막 잎 노드에  

도달할 때까지 반복한다. 이때 잎 노드는 서브 트리 중 가장 왼쪽  

자식노드를 의미한다. 

 그런 후 잎 노드에 대한 부모 노드의 오른쪽 서브트리를 방문한다.  

이때 왼쪽 서브트리의 방문이 모두 끝나면 근 노드의 오른쪽  

서브트리를 방문한다. 오른쪽 서브트리의 방문은 위 과정을 반복한다. 


 전위 운행 알고리즘 

 Void preorder(struct node * NODE) 

        if (NODE != NULL) 

        { 

                printf(“%c”, NODE -> data);  //근 노드 방문 

                preorder(NODE -> leftchild);  //왼쪽 서브트리 방문 

                preorder(NODE -> rightchild;  //오른쪽 서브트리 방문 

        } 

 




 중위 운행법(left-root-right)의 알고리즘 

 이진 트리의 근 노드에서 출발하여 먼저 왼쪽 서브트리에 대하여  

순환적으로 노드들을 방문한 후 더 이상 왼쪽 서브트리의 노드가  

없을 때까지 방문을 계속 한다. 

 그 다음 근 노드를 방문하고, 그후 오른쪽 서브트리를 순환적으로  

방문하고 모든 노드의 방문이 끝나면 운행을 종료한다. 



 후위 운행법(left-right-root)의 알고리즘 

 먼저 왼쪽 서브트리에 대하여 순환적으로 노드들을 방문한 후 왼쪽  

서브트리에서의 방문이 끝나면  오른쪽 서브트리를 순환적으로  

방문한다.   

 이때 오른쪽 서브트리의 마지막 잎노드까지 모두 방문한 후  

근 노드를 방문하여  운행을 종료한다. 이것은 원시 프로그램을  

컴파일시 중간 부호 형태로 변환시킬 때 주로 사용하는 방법이다. 



 후위 운행법(left-right-root)의 알고리즘 

 후위 운행 알고리즘 

 Void postorder(struct node * NODE) 

        if (NODE != NULL) 

        { 

                postorder(NODE -> leftchild);  //왼쪽 서브트리 방문 

                postorder(NODE -> rightchild;  //오른쪽 서브트리 방문 

                printf(“%c”, NODE -> data);  //근 노드 방문리 방문 


0123