|
|
Posted on 2011-03-22 14:25 乱78糟 阅读(1053) 评论(0) 编辑 收藏 引用 所属分类: 算法&数据结构
1 #include <stdio.h>
2#include <stdarg.h>
3
4#ifndef bool
5#define bool unsigned int
6#define false 0
7#define true 1
8#endif
9
10#ifndef NULL
11#define NULL 0
12#endif
13
14#define traversal_output
15
16  /**//* traversal order */
17typedef enum  {
18  NLR = 0, /**//* preorder */
19 LNR = 1, /**//* inorder */
20 LRN = 2 /**//* postorder */
21 }Order;
22
23typedef struct _BTNode{
24 struct BTNode *l_child;
25 struct BTNode *r_child;
26 void *data;
27}BTNode;
28
29BTNode *create_node(void)
30{
31 BTNode *node = (BTNode *)malloc(sizeof(BTNode));
32
33 if (node != NULL) {
34 node->data = NULL;
35 node->l_child = NULL;
36 node->r_child = NULL;
37 }
38
39 return node;
40}
41
42void destroy_node(BTNode *node)
43{
44 free(node);
45 node = NULL;
46}
47
48void bt_printf(const char *fmt, )
49{
50#ifdef traversal_output
51 va_list list;
52 char buf[256];
53 va_start(list, fmt);
54 vsnprintf(buf, sizeof(buf), fmt, list);
55 printf("%s", buf);
56 va_end(list);
57#endif
58}
59
60BTNode *insert_child(BTNode *parent, bool left, void *data)
61{
62 BTNode *node;
63 if (parent == NULL) {
64 return NULL;
65 }
66
67 if ((node = create_node()) == NULL) {
68 return NULL;
69 }
70
71 node->data = data;
72
73 if (left) {
74 parent->l_child = node;
75 }
76 else {
77 parent->r_child = node;
78 }
79
80 return node;
81}
82
83void remove_child(BTNode *parent, BTNode *node, bool destroy)
84{
85 if (parent == NULL || node == NULL) {
86 return;
87 }
88
89 if (parent->l_child == node) {
90 parent->l_child = NULL;
91 }
92 else if (parent->r_child == node) {
93 parent->r_child = NULL;
94 }
95 else {
96 return;
97 }
98
99 if (destroy) {
100 destroy_node(node);
101 }
102}
103
104BTNode *NLR_search(BTNode *parent, void *data)
105{
106 BTNode *node = NULL;
107
108 if (parent == NULL) {
109 return NULL;
110 }
111
112 bt_printf("->%d\n", *(int *)(parent->data));
113
114 //首先访问中间
115 if (parent->data == data){
116 return parent;
117 }
118
119 if ((node = NLR_search(parent->l_child, data)) == NULL) {
120 return NLR_search(parent->r_child, data);
121 }
122 return node;
123}
124
125BTNode *LNR_search(BTNode *parent, void *data)
126{
127 BTNode *node = NULL;
128
129 if (parent == NULL) {
130 return NULL;
131 }
132
133 //首先访问左边
134 node = LNR_search(parent->l_child, data);
135
136 bt_printf("->%d\n", *(int *)(parent->data));
137
138 if (node == NULL) {
139 if (parent->data == data) {
140 return parent;
141 }
142 else {
143 return LNR_search(parent->r_child, data);
144 }
145 }
146 return node;
147}
148
149BTNode *LRN_search(BTNode *parent, void *data)
150{
151 BTNode *node = NULL;
152
153 if (parent == NULL) {
154 return NULL;
155 }
156
157 //首先访问右边
158 node = LRN_search(parent->r_child, data);
159
160 if (node == NULL) {
161 node = LRN_search(parent->l_child, data);
162 if (node == NULL && parent->data == data) {
163 node = parent;
164 }
165 }
166
167 bt_printf("->%d\n", *(int *)(parent->data));
168
169 return node;
170}
171
172BTNode *find_node(BTNode *parent, void *data, Order order)
173{
174 if (order == NLR) {
175 return NLR_search(parent, data);
176 }
177 else if (order == LNR) {
178 return LNR_search(parent, data);
179 }
180 else if (order == LRN) {
181 return LRN_search(parent, data);
182 }
183 return NULL;
184}
185
186/**//*****************************************
187 * test code
188 *****************************************/
189
190//我们来找它
191void *target;
192
193BTNode *insert_binary_node(BTNode *parent, bool left, int num)
194{
195 int *data;
196 data = (int *)malloc(sizeof(int));
197 *data = num;
198 return insert_child(parent, left, (void *)data);
199}
200
201/**//* root(100)
202 * / \
203 * 1 2
204 * / / \
205 * 3 4 5
206 * / \ / \
207 * NULL 0 NULL NULL
208 */
209BTNode *create_binary_tree()
210{
211 BTNode *root, *node;
212
213 root = create_node();
214 root->data = (int *)malloc(sizeof(int));
215 *(int *)(root->data) = 100;
216
217 //构建左边树
218 node = insert_binary_node(root, true, 1);
219 node = insert_binary_node(node, true, 3);
220 node = insert_binary_node(node, false, 0);
221
222 //这就是我们要找的目标
223 target = node->data;
224
225 //构建右边树
226 node = insert_binary_node(root, false, 2);
227 insert_binary_node(node, true, 4);
228 insert_binary_node(node, false, 5);
229
230 return root;
231}
232
233void destroy_binary_tree(BTNode *root)
234{
235 //用LRN遍历并销毁每个节点
236}
237
238void main(int argc, char *argv[])
239{
240 BTNode *root, *node;
241
242 root = create_binary_tree();
243
244 node = find_node(root, target, NLR);
245 printf("NLR\ttarget=%d\n\n", *(int *)(node->data));
246
247 node = find_node(root, target, LNR);
248 printf("LNR\ttarget=%d\n\n", *(int *)(node->data));
249
250 node = find_node(root, target, LRN);
251 printf("LRN\ttarget=%d\n\n", *(int *)(node->data));
252
253 destroy_binary_tree(root);
254
255 getchar();
256}
|