트리(Tree)
트리(Tree)?
트리는 비 선형(Non-linear) 자료구조로 root(부모), leaf(자식)로 구성됩니다.
트리의 레벨은 깊이를 의미하며, 높이는 가장 높은 레벨을 의미합니다.
이진트리?
이진트리 : 이진트리는 가장 널리 쓰이는 트리의 형태로, 자식을 1~2개만 가지는 트리
이진트리의 레벨이 d, 노드의 수가 N이라고하면
아래 식을 만족합니다.
완전 이진트리?
최 하위 노드를 제외하고 자식노드가 꽉찬 트리
연결리스트를 이용한 이진트리 예제
트리는 비 선형구조라 순서가 없지만, 자동으로 입력하기위해 순서를 부여 하였습니다.
tree로 사용할 구조체
값, 자식 노드(left, right)와
값을 자동으로 넣기 위해 next 할당
초기 root와 부모노드를 위한 변수 parent 선언
parent 노드를 지정해주면서 left, right에 값을 할당
#include "stdio.h"
#include "stdlib.h"
typedef struct _tree
{
char value;
struct _tree *left;
struct _tree *right;
struct _tree *next;
} tree;
tree *root, *parent;
초기화 함수
void init_tree(void){
root = (tree*)malloc(sizeof(tree));
root->left = NULL;
root->right = NULL;
root->value = '\0';
parent = root;
}
트리에 값을 넣는 함수
임시 트리에 값을 할당하고, 최초 root인 경우를 제외하고는 left, right에 할당
tree *addVaule(char value){
tree *new;
new = (tree*)malloc(sizeof(tree));
new->value = value;
new->left = NULL;
new->right = NULL;
if(parent->value != '\0' && parent->left != NULL && parent->right != NULL){
if(!parent->right->next)parent->right->next = new;
parent = parent->next;
}
if(parent->value=='\0'){ // root
parent->value = new->value;
}else if(parent->left == NULL){ // left
parent->left = new;
if(!parent->next)parent->next = new;
}else{ // right
parent->right = new;
if(!parent->left->next)parent->left->next = new;
}
}
순서대로 전위, 중위, 후위 순회 방식으로 출력하는 함수
재귀 방식을 사용해서 출력 합니다.
void printPreorder(tree *t){
printf("%-2c",t->value);
if(t->left)printPreorder(t->left);
if(t->right)printPreorder(t->right);
}
void printInorder(tree *t){
if(t->left)printInorder(t->left);
printf("%-2c",t->value);
if(t->right)printInorder(t->right);
}
void printPostorder(tree *t){
if(t->left)printPostorder(t->left);
if(t->right)printPostorder(t->right);
printf("%-2c",t->value);
}
메인함수
트리를 초기화 한 후 A~G 문자를 삽입 한 후
전위, 중위, 후위 순회에 맞게 출력합니다.
void main(){
init_tree();
char treeValue[] = {'A','B','C','D','E','F','G'};
for(int i=0; i<sizeof(treeValue); i++){
addVaule(treeValue[i]);
}
printf("PreOrder : ");
printPreorder(root);
printf("\nInOrder : ");
printInorder(root);
printf("\nPostOrder : ");
printPostorder(root);
}
아래와 같은 이진 트리를 생성하고 순회합니다.
실행결과
참고 : C로 배우는 알고리즘 (이재규)
관련 포스팅
'언어 > Data Strcuture' 카테고리의 다른 글
| [C] 삽입 정렬(Insertion Sort) (0) | 2019.04.19 |
|---|---|
| [C] 선택 정렬(Selection Sort) (0) | 2019.04.19 |
| [C] 큐(Queue) (2) | 2019.04.01 |
| [C] 스택(Stack) (1) | 2019.03.29 |
| [C] 연결리스트(LinkedList) (0) | 2019.03.28 |