카테고리 없음
이진트리순회 - Binary tree traversal
bo97037
2013. 3. 24. 16:28
| 이진트리순회란 트리 내의 각 노드를 정확히 한번씩 방문하는 것을 말함. 여러가지 방법(6가지)이 있으나 대부분 사용하는 것은 3가지 정도다. 중위순회(left, data, right), 전위순회(data, left, right), 후위순회(left, right, data) 등이 있다. 각각의 출력값은 모두 다르다. 다음과 같이 이진트리가 되어 있다고 하자! 
잘 생각해보면 쉽게 이해 할 수 있다. 출력해보면 다음과 같이 출력이 된다. 중위순회: 4 2 5 1 6 3 7 전위순회: 1 2 4 5 3 6 7 후위순회: 4 5 2 6 7 3 1 이해가 되지 않으면 코드를 보고 따라하길 바란다.
#include <iostream>
using namespace std; struct tree_node{
tree_node *left_child; int data;
tree_node *right_child;
}; tree_node *root; // 이진 트리 생성(구조체로 반환)
tree_node *create_node(int data){
tree_node *node = new tree_node;
node->left_child = NULL;
node->data = data;
node->right_child = NULL;
return node;
} // 중위 순회
void inorder(tree_node *ptr){
if(ptr){ inorder(ptr->left_child);
cout<<ptr->data<<" ";
inorder(ptr->right_child);
}
} // 전위 순회
void preorder(tree_node *ptr){
if(ptr){
cout<<ptr->data<<" ";
preorder(ptr->left_child);
preorder(ptr->right_child);
}
} // 후위 순회
void postorder(tree_node *ptr){
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
cout<<ptr->data<<" ";
}
} // 메모리 반환
void FreeEnd(tree_node *ptr){
if(ptr){
//재귀함수로 메모리를 해제
FreeEnd(ptr->left_child);
FreeEnd(ptr->right_child);
free(ptr);
}
} void main(){
// 이진트리 생성
root = create_node(1);
root->left_child = create_node(2);
root->right_child = create_node(3);
root->left_child->left_child = create_node(4);
root->left_child->right_child = create_node(5);
root->right_child->left_child = create_node(6); root->right_child->right_child = create_node(7); cout<<endl<<"중위순회: ";
inorder(root); cout<<endl<<"전위순회: ";
preorder(root); cout<<endl<<"후위순회: ";
postorder(root); //메모리 반환
FreeEnd(root);
}
|
