- 트리 : 계층적인 구조를 나타내는 자료구조
- 리스트, 스택, 큐 등은선형 구조
- 트리는 부모-자식 관계의 노드들로 이루어짐
이진 트리
- 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리
- 서브트리는 공집합일 수 있음
노드의 개수가 n개이면 간선의 개수는 n-1
높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 (2^h)-1개의 노드를 가짐
n개의 노드를 가지는 이진 트리의 높이
링크 표현법 : 포인터를 이용해 부모노드가 자식노드를 가리키게 하는 방법
링크의 구현
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
}TreeNode
void main(){
TreeNode *n1, *n2, *n3;
n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));
n1->data = 10;
n1->left = n2;
n1->rigth = n3;
n2->data = 20;
n2->left = NULL;
n2->rigth = NULL;
n3->data = 30;
n3->left = NULL;
n3->rigth = NULL;
}
순회
- 트라ㅣ의 노드들을 체계적으로 방문하는 것
루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
preorder(TreeNode *root){
if(root){
printf("%d", root->data);
preorder(root->left);
preorder(root->right);
}
}
왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
inorder(TreeNode *root){
if(root){
inorder(root->left);
printf("%d", root->data);
inorder(root->rigth);
}
}
왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
postorder(TreeNode *root){
if(root){
postorder(root->left);'
postorder(root->rigth);
printf("%d", root);
}
}
void level_order(TreeNode *root){
QueueType q;
init_queue(&q);
if(ptr == NULL) return;
equeue(&q, ptr);
while(!is_empty(&q)){
ptr = dequeue(&q);
printf(" [%d}] ", ptr->data);
if(ptr->left)
enqueue(&q, ptr->left);
if(ptr->right)
enqueue(&q, ptr->right);
}
}
TreeNode *searcH(TreeNode *node, int key){
if( node == NULL)
return NULL;
if( key == node->key)
return node;
else if( key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
TreeNode *search(TreeNode *node, int key){
while(node != NULL){
if( key == node->key)
return node;
else if( key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
return NULL;
}
void insert_node(TreeNode **root, int key){
TreeNode *p, *t;
TreeNode *n;
t = *root;
p = NULL;
while( t!= NULL ){
if( key == t->key )
return;
p = t;
if( key < t->key )
t = t->left;
else
t = t->right;
}
n = (TreeNode *)malloc(sizeof(TreeNode));
if( n == NULL )
return;
n->key = key;
n->left, n->right = NULL;
if( p != NULL ){
if( key < p->key )
p->left = n;
else
p->right = n;
else
*root = n;
}
void delete_node(TreeNode **root, int key){
TreeNode *p, *child, *succ, *succ_p, *t;
p = NULL;
t = *root;
while( t != NULL && t->key != key ){
p = t;
t = (key < t->key) ? t->left : t->right;
}
if( t == NULL ){
printf("key is not in the tree");
return;
}
if( (t->left == NULL) && (t->right == NULL) ){
if( p != NULL){
if( p->left == t )
p->left = NULL;
else
p->right = NULL;
}
else
*root = NULL;
}
else if( (t->left == NULL) || (t->right == NULL) ){
child = (t->left != NULL) ? t->left : t->right;
if( p != NULL ){
if( p->left == t )
p->left = child;
else
p->right = child;
}
else
*root = child;
}
else
succ_p = t;
succ = t->right;
while( succ->left != NULL ){
succ_p = succ;
succ = succ->left;
}
if( succ_p->left == succ )
succ_p->left = succ->right;
else
succ_p->right = succ->right;
t->key = succ-key;
t = succ;
}
tree(t);
}
TreeNode *new_node(int item){
TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode *insert_node(TreeNode *node, int key){
if( node == NULL )
return new_node(key);
if( key < node->key )
node->left = insert_node(node->left, key);
else if( key > node->key)
node->right = insert_node(node->right, key);
return node;
}
TreeNode *min_value_node(TreeNode *node){
TreeNode *current = node;
while( current->left != NULL )
current = current->left;
return current;
}
TreeNode *delete_node(TreeNode *root, int key){
if( root == NULL )
return root;
if( key < root->key )
root->left = delete_node(root->left, key);
else if( key > root->key )
root->right = delete_node(root->right, key);
else{
if( root->left == NULL ){
TreeNode *temp = root->right;
free(root);
return temp;
}
else if( root->right == NULL ){
TreeNode *temp = root->left;
free(root);
return temp;
}
TreeNode *temp = min_value_node(root->right);
root->key = temp->key;
root->right = delete_node(root->right, temp->key);
}
return root;
}