Árbol de búsqueda binario no recursivo / iterativo en C (tarea)

¿Cómo puedo crear / eliminar un nodo en un árbol de búsqueda binario utilizando un algoritmo iterativo en C?

Inserción iterativa:

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; } 

Inserción y eliminación iterativa en 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; } 

Buen post. Sólo una sugerencia. Creo que encontrar un valor mínimo en un BST no tiene que atravesar el subárbol correcto. El valor mínimo debe estar en el subárbol izquierdo o en el propio nodo (en caso de que si el subárbol izquierdo es nulo). La función find_minimum_value se puede optimizar si se elimina el recorrido del subárbol derecho.

 int find_minimum_value(bst_t *ptr) { while(ptr->left) { ptr = ptr->left; } return ptr->data; } 

En C, puede convertir los punteros en el árbol al tipo intptr_t y realizarles operaciones a nivel de bits.

A medida que se desplaza por el árbol, puede almacenar el puntero ‘padre’ de un nodo al ubicarlo con el puntero con el que se cruzó. Luego puede realizar una copia de respaldo del árbol al almacenar la dirección del nodo del que proviene con el puntero modificado.

Un ejemplo práctico de esta técnica tradicional se encuentra en http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

Dada la capacidad de atravesar el árbol sin recursión, puede crear versiones iterativas de cualquiera de los algoritmos basados ​​en atravesar el árbol.