大漠落日

while(!dead) study++;
posts - 46, comments - 126, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

二叉树三种方式遍历小例子

Posted on 2011-03-22 14:25 乱78糟 阅读(983) 评论(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, true1);
219    node = insert_binary_node(node, true3);
220    node = insert_binary_node(node, false0);
221
222    //这就是我们要找的目标
223    target = node->data;
224    
225    //构建右边树
226    node = insert_binary_node(root, false2);
227    insert_binary_node(node, true4);
228    insert_binary_node(node, false5);
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}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理