트리 순회법
- 트리 순회 방법에는 3가지가 있다.
- 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)
전위 순회법(Preorder Traversal)
1. 루트 노드부터 시작해서 아래로 내려 오면서
2. 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면
3. 오른쪽 하위 트리를 방문하는 방식
중위 순회법(Inorder Traversal)
- 트리는 하위 트리의 집합이라고 할 수 있고 하위 트리 역시 또 다른 하위 트리의 집합이라고 할 수 있다.
- 따라서 아래와 같은 방법으로 탐색할 수 있다.
1. 왼쪽 하위 트리부터 시작해서
2. 루트를 거쳐
3. 오른쪽 하위 트리를 방문하는 방법
- 응용 사례 : 수식 트리(Expression Tree), 중위 표기식
- (1 * 2) + (7 - 8)을 수식 트리로 표현하면 다음 그림과 같이 나타낼 수 있다.
후위 순회법(Postorder Traversal)
- 전위 순회의 반대
1. 왼쪽 하위 트리부터 시작해서
2. 오른쪽 형제 노드를 방문 후
3. 루트 노드를 방문하는 방법.
- 응용 사례 : 후위 표기식. 후위 순회법을 통해 출력되는 노드를 살펴보면 후위 표기식으로 나타난다.
- 1 2 * 7 8 - +
출처 : http://warmz.tistory.com/619
다음은 순회를 적용한 간단 이진 트리 예제입니다.
가장 핵심은 void DeleteTree(BTreeNode * bt)함수인데 이 함수는 모든 트리 노드를 삭제하는 역할을 합니다.
이때 후위 순회를 이용한다는 점이 가장 중요합니다.
BinaryTree.h
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
typedef int BTData
typedef struct _bTreeNode{
BTData data
struct _bTreeNode *left
struct _bTreeNode *right
}BTreeNode
BTreeNode * MakeBTreeNode(void);//빈노드생성함수
BTData GetData(BTreeNode * bt);//bt의data 반환함수
void SetData(BTreeNode * bt, BTData data);//bt의data에입력받은data로세팅
BTreeNode * GetLeftSubTree(BTreeNode * bt);//왼쪽서브트리를가져옴
BTreeNode * GetRightSubTree(BTreeNode * bt);//오른쪽서브트리를가져옴
void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub);//왼쪽서브트리를만듬
void MakeRightSubTree(BTreeNode * main,BTreeNode * sub);//오른쪽서브트리를만듬
void DeleteTree(BTreeNode * bt);
typedef void (*VisitFuncPtr)(BTData data);//함수포인터를쉽게쓰기위해서typedef를함
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);//전위순회함수
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);//중위순회함수
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);//후위순회함수
#endif
BinaryTree.c
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
BTreeNode * MakeBTreeNode(void){
BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
nd->left = NULL
nd->right = NULL
return nd
}
BTData GetData(BTreeNode * bt){
return bt->data
}
void SetData(BTreeNode * bt, BTData data){
bt->data = data
}
BTreeNode * GetLeftSubTree(BTreeNode * bt){
return bt->left
}
BTreeNode * GetRightSubTree(BTreeNode * bt){
return bt->right
}
void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub){
if(main->left != NULL)
free(main->left);
main->left = sub
}
void MakeRightSubTree(BTreeNode * main,BTreeNode * sub){
if(main->right != NULL)
free(main->right);
main->right = sub
}
//전위순회
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action){
if(bt== NULL)
return
action(bt->data);//부모먼저출력하고
PreorderTraverse(bt->left, action);//왼쪽출력
PreorderTraverse(bt->right, action);//오른쪽출력
}
//중위순회
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action){
if(bt == NULL)
return
InorderTraverse(bt->left, action);//왼쪽먼저출력하고
action(bt->data);//부모를중간에출력해서중위임
InorderTraverse(bt->right, action);//오른쪽출력
}
//후위순회
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action){
if(bt == NULL)
return
PostorderTraverse(bt->left, action);//왼쪽부터출력
PostorderTraverse(bt->right, action);//오른쪽출력
action(bt->data);//마지막에부모를출력해서후위임
}
void DeleteTree(BTreeNode * bt){
if(bt == NULL)
return
DeleteTree(bt->left);
DeleteTree(bt->right);
printf("del data : %d \n",bt->data);
free(bt);
}
main.c
#include <stdio.h>
#include "BinaryTree.h"
void ShowIntData(int data);
int main(){
BTreeNode * bt1 = MakeBTreeNode();//노드bt1 생성
BTreeNode * bt2 = MakeBTreeNode();
BTreeNode * bt3 = MakeBTreeNode();
BTreeNode * bt4 = MakeBTreeNode();
SetData(bt1, 1);//bt1에데이터저장
SetData(bt2, 2);//bt2에데이터저장
SetData(bt3, 3);//bt3에데이터저장
SetData(bt4, 4);//bt4에데이터저장
MakeLeftSubTree(bt1, bt2);//bt2를bt1의왼쪽자식으로
MakeRightSubTree(bt1, bt3);//bt3를bt1의오른쪽자식노드로
MakeLeftSubTree(bt2, bt4);//bt4를bt2의왼쪽자식노드로
PreorderTraverse(bt1, ShowIntData);
printf("\n");
InorderTraverse(bt1, ShowIntData);
printf("\n");
PostorderTraverse(bt1, ShowIntData);
printf("\n");
DeleteTree(bt1);
printf("\n");
//PostorderTraverse(bt1, ShowIntData);
return 0;
}
void ShowIntData(int data){
printf("%d ", data);
}
출력 화면
'프로그래밍 > C언어 C++언어' 카테고리의 다른 글
| C/C++ - 함수포인터 (펌자료) (0) | 2015.01.25 |
|---|---|
| C/C++ - C를 이용한 간단한 이진 트리 예제 (0) | 2015.01.25 |
| C/C++ - STL 라이브러리 string 함수 사용법 (3) | 2014.01.28 |