C中的非递归/迭代二进制搜索树（家庭作业）
如何在C中使用迭代算法在二进制搜索树中创建/删除节点？
迭代插入：
struct tree_node *Insert_Element (struct tree_node *root, void *key, void *data) { struct tree_node *new_node, *node; node = root; do { switch (compare(key, node->key)) { case -1: { if (node->left == NULL) { if ((new_node = create_node(key, data)) == NULL) { return NULL; } node->left = new_node; return new_node; } node = node->left; } break; case 1: { if (node->right == NULL) { if ((new_node = create_node(key, data)) == NULL) { return NULL; } node->right = new_node; return new_node; } node = node->right; } break; default: { return node; } } } while (node != NULL); return NULL; } BST中的迭代插入和删除
struct bst { int data; struct bst *left; struct bst *right; }; typedef struct bst bst_t; bst_t *get_new_node(int val) { bst_t *node = (bst_t *) malloc(sizeof(bst_t)); node->data = val; node->left = NULL; node->right= NULL; return node; } bst_t *insert(bst_t *root, int val) { if(!root) return get_new_node(val); bst_t *prev = NULL, *ptr = root; char type = ' '; while(ptr) { prev = ptr; if(val < ptr->data) { ptr = ptr->left; type = 'l'; } else { ptr = ptr->right; type = 'r'; } } if(type == 'l') prev->left = get_new_node(val); else prev->right = get_new_node(val); return root; } int find_minimum_value(bst_t *ptr) { int min = ptr ? ptr->data : 0; while(ptr) { if(ptr->data < min) min = ptr->data; if(ptr->left) { ptr = ptr->left; } else if(ptr->right) { ptr = ptr->right; } else ptr = NULL; } return min; } bst_t *delete(bst_t *root, int val) { bst_t *prev = NULL, *ptr = root; char type = ' '; while(ptr) { if(ptr->data == val) { if(!ptr->left && !ptr->right) { // node to be removed has no children's if(ptr != root && prev) { // delete leaf node if(type == 'l') prev->left = NULL; else prev->right = NULL; } else root = NULL; // deleted node is root } else if (ptr->left && ptr->right) { // node to be removed has two children's ptr->data = find_minimum_value(ptr->right); // find minimum value from right subtree val = ptr->data; prev = ptr; ptr = ptr->right; // continue from right subtree delete min node type = 'r'; continue; } else { // node to be removed has one children if(ptr == root) { // root with one child root = root->left ? root->left : root->right; } else { // subtree with one child if(type == 'l') prev->left = ptr->left ? ptr->left : ptr->right; else prev->right = ptr->left ? ptr->left : ptr->right; } } free(ptr); } prev = ptr; if(val < ptr->data) { ptr = ptr->left; type = 'l'; } else { ptr = ptr->right; type = 'r'; } } return root; }
好贴。 只是一个建议。 我相信，在BST中找到最小值不必遍历正确的子树。 最小值必须位于左子树或节点本身（如果左子树为空，则为最小值）。 如果删除了右子树遍历，则可以优化函数find_minimum_value。
int find_minimum_value(bst_t *ptr) { while(ptr->left) { ptr = ptr->left; } return ptr->data; }
在C中，您可以将树中的指针intptr_t为intptr_t类型并对它们执行按位操作。
当您遍历树时，可以通过使用您遍历的指针对其进行xored来存储节点的“父”指针。 然后，您可以通过使用修改后的指针对来自的节点的地址进行xoring来遍历树。
这个传统技术的一个有效例子是http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers
鉴于能够在没有递归的情况下遍历树，您可以基于遍历树创建任何算法的迭代版本。