/* * binary_tree_bfs.c * * Created on: May 20, 2011 * Author: zjshen */ #include #include struct Node { int val; struct Node* left; struct Node* right; }; struct NodeQueue { struct Node* node; struct NodeQueue* next; }; void construct_binary_tree(struct Node*, int, int, char**); struct Node* construct_child(int, int, char**); void print_binary_tree(struct NodeQueue*); void destruct_binary_tree(struct Node*); int main(int argc, char** argv) { struct Node* root = (struct Node*) malloc(sizeof(struct Node)); root->val = atoi(argv[1]); root->left = NULL; root->right = NULL; construct_binary_tree(root, 0, argc - 1, argv + 1); struct NodeQueue* head = (struct NodeQueue*) malloc(sizeof(struct NodeQueue)); head->node = root; head->next = NULL; print_binary_tree(head); destruct_binary_tree(root); return 0; } void construct_binary_tree(struct Node* root, int base, int limit, char** values) { struct Node* left_child = construct_child(base * 2 + 1, limit, values); struct Node* right_child = construct_child(base * 2 + 2, limit, values); if (left_child != NULL) { root->left = left_child; construct_binary_tree(left_child, base * 2 + 1, limit, values); } if (right_child != NULL) { root->right = right_child; construct_binary_tree(right_child, base * 2 + 2, limit, values); } } struct Node* construct_child(int index, int limit, char** values) { int val = -1; if (index val = val; child->left = NULL; child->right = NULL; return child; } return NULL; } void print_binary_tree(struct NodeQueue* head) { struct NodeQueue* tail = head; struct NodeQueue* node; while (head != NULL) { if (head->node->left != NULL) { node = (struct NodeQueue*) malloc(sizeof(struct NodeQueue)); node->node = head->node->left; node->next = NULL; tail->next = node; tail = node; } if (head->node->right != NULL) { node = (struct NodeQueue*) malloc(sizeof(struct NodeQueue)); node->node = head->node->right; node->next = NULL; tail->next = node; tail = node; } printf("%d ", head->node->val); node = head; head = head->next; free(node); } printf("\n"); } void destruct_binary_tree(struct Node* root) { if (root->left != NULL) { destruct_binary_tree(root->left); } if (root->right != NULL) { destruct_binary_tree(root->right); } free(root); }