그 외 공부/Algorithm
# 8_Contacts with BST
ssangeun
2017. 11. 5. 18:49
# The source
|
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 |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
struct node
{
char name[30];
char phone_n[30];
struct node * left;
struct node * right;
};
struct node * root = 0;
void addToBST(char * name, char * phone_n)
{
struct node * cur = (struct node *)malloc(sizeof(struct node));
char * _name = (char *)malloc(sizeof(name)); char * _phone = (char *)malloc(sizeof(phone_n));
strcpy_s(cur->name, strlen(name) + 1, name); strcpy_s(cur->phone_n, strlen(phone_n) + 1, phone_n);
cur->left = 0; cur->right = 0;
if (root == 0)
{
root = cur;
}
else
{
struct node * temp = root;
while (1)
{
if (strcmp(temp->name, cur->name) > 0) //left
{
if (temp->left == 0)
{
temp->left = cur;
return;
}
else
{
temp = temp->left;
}
}
else //right
{
if (temp->right == 0)
{
temp->right = cur;
return;
}
else
{
temp = temp->right;
}
}
}
}
}
struct node * findLeast(struct node * node)
{
struct node * cur = node;
while (cur->left != 0)
{
cur = cur->left;
}
return cur;
}
struct node * removeNode(struct node * node_, char * key)
{
if (node_ == 0)
{
return 0;
}
if (strcmp(key, node_->name) == 0)
{
if (node_->left == 0 && node_->right == 0)
{
free(node_);
return 0;
}
else if (node_->left == 0) // 오른쪽 자식만 있는 경우
{
struct node * ret = node_->right;
free(node_);
return ret;
}
else if (node_->right == 0) // 왼쪽 자식만 있는 경우
{
struct node * ret = node_->left;
free(node_);
return ret;
}
else // 두쪽다 자식이 있는 경우
{
struct node * toReplace = findLeast(node_->right);
memset(node_->name, '\0', sizeof(node_->name));
memset(node_->phone_n, '\0', sizeof(node_->phone_n));
strcpy_s(node_->name, strlen(toReplace->name) + 1, toReplace->name);
strcpy_s(node_->phone_n, strlen(toReplace->phone_n) + 1, toReplace->phone_n);
node_->right = removeNode(node_->right, toReplace->name);
return node_;
}
}
else if (strcmp(key , node_->name) < 0)
{
node_->left = removeNode(node_->left, key);
return node_;
}
else
{
node_->right = removeNode(node_->right, key);
return node_;
}
}
void printBST(struct node * node)
{
if (node == 0)
{
return;
}
printBST(node->left);
printf("%s -> ", node->name);
printBST(node->right);
}
void main()
{
addToBST("one","010-1111-1111");
addToBST("two","010-2222-2222");
addToBST("three","010-3333-3333");
addToBST("four","010-4444-4444");
addToBST("five","010-5555-5555");
printBST(root);
printf("\n");
removeNode(root, "one");
printf("BST after removing root one : ");
printBST(root);
printf("\n");
} |
cs |
* 동적할당을 할 때에 사용 후에 free를 하면 그 주소값은 다시 사용이 불가합니다. 따라서 구조체의 name, phone number를 받아오는 객체는 포인터로 사용하지 않고 배열을 사용하였습니다.
# The result
