C中的非遞歸/迭代二叉搜索樹（作業）

Question

如何使用C中的迭代算法在二叉搜索樹中創建/刪除節點？

Answer 1

多次插入：

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

Answer 2

在C語言中，你可以在樹中投的指針intptr_t類型和執行位操作他們。

當您沿着樹遍歷時，可以通過將它與您遍歷的指針一起存儲來存儲節點的「父」指針。然後，您可以通過使用修改的指針對來自節點的地址進行xoring來遍歷樹。

一個工作這種傳統技術的例子是在http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

鑑於遍歷樹沒有遞歸的能力，那麼你就可以創建任何基於遍歷樹算法迭代版本。

Answer 3

多次插入&缺失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; 
} 

Answer 4

尼斯後。只是一個建議。我相信，在BST中找到最小值不需要遍歷右側的子樹。最小值必須位於左側子樹或節點本身（如果左側子樹爲空）。函數find_minimum_value可以優化，如果右子樹遍歷被刪除。

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