본문 바로가기
Data Structure/Sample Code

Tree

The_j.n 2015. 8. 19. 21:32

Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h>
#include <malloc.h>
struct Node
{
    struct Node* left_link;
    int data;
    struct Node* right_link;
};
typedef struct Node Tree;
 
Tree * Get_Node();
void insert_data(Tree ** root, int data);
void print_data(Tree * root);
void search_data(Tree * root,int data);
void delete_data(Tree ** root, int data);
 
int main()
{
    Tree * root = NULL;
    int i;
    int data[19] = {15,10,27,8,14,2,9,13,4,3,5,25,30,18,26,16,20,28,33};
 
    for(i=0;i<19;i++)
        insert_data(&root,data[i]);
    search_data(root,9);
    delete_data(&root,14);
    delete_data(&root,15);
    delete_data(&root,5);
    print_data(root);
    puts("");
 
    return 0;
}
 
 
 
Tree * Get_Node()
{
    Tree * tmp = (Tree*)malloc(sizeof(Tree));
    tmp->left_link = NULL;
    tmp->right_link = NULL;
    return tmp;
}
 
void insert_data(Tree ** root, int data)
{
    if(*root == NULL){
        *root = Get_Node();
        (*root)->data = data;
        return ;
    }
    
    if((*root)->data < data)
        insert_data(&(*root)->right_link,data);    
    else 
        insert_data(&(*root)->left_link,data);
}
 
 
 
void print_data(Tree * root)
{
    if(root==NULL)
        return ;
 
    print_data(root->left_link);
    printf("%d ",root->data);
    print_data(root->right_link);
}
 
void preorder_traversal(Tree * root)
{
    if(root==NULL)
        return ;
 
    printf("%d ",root->data);
    preorder_traversal(root->left_link);
    preorder_traversal(root->right_link);
}
 
void inorder_traversal(Tree * root)
{
    if(root==NULL)
        return ;
 
    inorder_traversal(root->left_link);
    printf("%d ",root->data);
    inorder_traversal(root->right_link);
}
 
void postorder_traversal(Tree * root)
{
    if(root==NULL)
        return ;
 
    postorder_traversal(root->left_link);
    postorder_traversal(root->right_link);
    printf("%d ",root->data);
}
 
 
 
void delete_data(Tree ** root, int data){
    Tree * tmp= NULL;
 
    if(*root==NULL)
        return ;
 
    if((*root)->data == data)
    {
        tmp = *root;
        if((*root)->left_link == NULL && (*root)->right_link ==NULL)
        {
            (*root) = NULL;
        }
        else if((*root)->left_link != NULL && (*root)->right_link !=NULL)
        {
Tree * tmp2 = *root;
tmp = *root;
            *root = (*root)->left_link;
            while(tmp2->right_link !=NULL){
                tmp2 = (*root)->right_link;
            }
            tmp2->right_link = tmp->right_link;
        }
        else
        {
            if((*root)->left_link != NULL)
                *root = (*root)->left_link;
            else
                *root = (*root)->right_link;
        }
 
        free(tmp);
        return ;
    }
 
    if((*root)->data > data)
        delete_data(&(*root)->left_link,data);
    else
        delete_data(&(*root)->right_link,data);
}
 
 
 
void search_data(Tree * root,int data)
{
    if(root==NULL)
        return;
 
    if(root->data == data)
    {
        printf("찾으시는 데이터는 %d번지에 있습니다 \n",&root->data);
        return ;
    }
 
    if(root->data > data)
        search_data(root->left_link,data);
    else
        search_data(root->right_link,data);
}
cs


저작자표시 비영리 변경금지

'Data Structure > Sample Code' 카테고리의 다른 글

Queue 응용  (0) 2015.08.19
LinkedList  (0) 2015.08.19
Queue  (0) 2015.08.19
Stack  (0) 2015.08.19

'Data Structure/Sample Code' Related Articles

티스토리툴바