Minwoo Dev.
[자료구조] 이진트리(연결리스트), 전위순회, 중위순회, 후위순회 - C 본문
728x90
반응형
SMALL
이진트리
이진트리는 완전 이진트리, 포화이진트리, 일반 이진트리
위를 바탕으로 기본적인 코드를 작성해보겠다.
기본 코드
#include<stdio.h>
#include<stdlib.h>
typedef struct _tree{
struct _tree *left;
int data;
struct _tree *right;
} Tree;
void AddData(Tree **position, int value) {
*position = (Tree *)malloc(sizeof(Tree));
(*position)->data = value;
(*position)->left = NULL;
(*position)->right = NULL;
}
void initData(Tree **head) {
AddData(head, 3);
AddData(&((*head)->left), 4);
AddData(&((*head)->left->left), 9);
AddData(&((*head)->left->right), 5);
AddData(&((*head)->right), 1);
AddData(&((*head)->right->left), 7);
AddData(&((*head)->right->left->right), 2);
}
int main(void) {
Tree *head = NULL;
initData(&head);
return 0;
}
위 코드를 실행하면 아래와 같은 형태가 나온다.
이제 위 기본 형식에 대해서 전위 순회, 중위 순회, 후위 순회를 실행하는 코드를 작성해보겠다.
전위 순회
- VLR (View - Left - Right) : 조회, 왼쪽 요소, 오른쪽 요소 순으로 진행한다.
- 위 데이터로는 3 -> 4 -> 9 -> 5 -> 1 -> 7 -> 2 순서로 조회된다.
중위 순회
- LVR (Left - View - Right) : 왼쪽 요소, 조회, 오른쪽 요소 순으로 진행한다.
- 위 데이터로는 9 -> 4 -> 5 -> 3 -> 7 -> 2 -> 1 순서로 조회된다.
후위 순회
- LRV (Left - Right - View) : 왼쪽 요소, 오른쪽 요소, 조회 순으로 진행한다.
- 위 데이터로는 9 -> 5 -> 4 -> 2 -> 7 -> 1 -> 3 순서로 조회된다.
실행 코드
#include<stdio.h>
#include<stdlib.h>
typedef struct _tree{
struct _tree *left;
int data;
struct _tree *right;
} Tree;
void AddData(Tree **position, int value) {
*position = (Tree *)malloc(sizeof(Tree));
(*position)->data = value;
(*position)->left = NULL;
(*position)->right = NULL;
}
void initData(Tree **head) {
AddData(head, 3);
AddData(&((*head)->left), 4);
AddData(&((*head)->left->left), 9);
AddData(&((*head)->left->right), 5);
AddData(&((*head)->right), 1);
AddData(&((*head)->right->left), 7);
AddData(&((*head)->right->left->right), 2);
}
void preorder_traverser(Tree *head) {
if (head != NULL) {
printf("%d->", head->data);
preorder_traverser(head->left);
preorder_traverser(head->right);
}
}
void inorder_traverser(Tree *head) {
if (head != NULL) {
inorder_traverser(head->left);
printf("%d->", head->data);
inorder_traverser(head->right);
}
}
void postorder_traverser(Tree *head) {
if (head != NULL) {
postorder_traverser(head->left);
postorder_traverser(head->right);
printf("%d->", head->data);
}
}
int main(void) {
Tree *head = NULL;
initData(&head);
printf("Preorder: ");
preorder_traverser(head);
printf("\n");
printf("Inorder: ");
inorder_traverser(head);
printf("\n");
printf("Postorder: ");
postorder_traverser(head);
printf("\n");
return 0;
}
실행 결과
728x90
반응형
LIST
'자료구조' 카테고리의 다른 글
[자료구조] 그래프(Graph), 인접 행렬, 인접 리스트 (0) | 2024.08.12 |
---|---|
[자료구조] 이진 탐색 트리(Binary Search Tree) (0) | 2024.08.12 |
[자료구조] 완전 이진트리 구현 (배열) - C (0) | 2024.08.10 |
[자료구조] 원형 배열 큐를 이용해 전위식 계산하기 - C (0) | 2024.08.08 |
[자료구조] 스택을 이용해 중위식을 후위식으로 변환하기 (0) | 2024.08.07 |