[C言語実装]二叉ルックアップツリーの基本操作を実現(反復版)

このブログでは、ツリーの定義が再帰的に実現されているため、再帰的に上記の操作を反復的に完了することは、再帰的に容易に実現できるという考え方を記録しています.
インプリメンテーションの挿入
親ノードの親ノードを手動で記録する必要があります.親ノードの子ツリーを新しいノードに挿入するノードが親ノードの左サブツリーか右サブツリーかを指すため、サイズを比較することで決定できます.

void SearchTreeInsert_ByLooP(SearchTreeNode* root, SearchTreeType key)
{
  SearchTreeNode* pre_node = root;
  SearchTreeNode* node = root;
  for(node = root; node != NULL;  )
  {
    if(node->key > key)
    {
      pre_node = node;
      node = node->rchild;
    }
   else  if(node->key < key)
    {
      pre_node = node;
      node = node->lchild;
    }
   else if(node->key == key)
   {
     break;
   }
  }
  //        
  if(node == NULL)
  {
    node  = (SearchTreeNode*)malloc(sizeof(SearchTreeNode));
    node->key = key;
    node->lchild = NULL;
    node->rchild = NULL;
      //              
    if(pre_node->key < node->key)
    {
      pre_node->rchild = node;
    }
    else 
    {
      pre_node->lchild = node;
    }
  }
}

検索
検索は何もなくて、再帰と同じで、大きさを比較して、ループを終了する時node=NULLは検索が命中していないことを表します
削除
再帰バージョンの削除は複雑で反復にはもっと難しいですが、考え方は2つのノードを記録します.pre_Node(親ノード)node(現在のノード)、nodeがpreであることをサイズに基づいて比較する必要があるNodeの左サブツリーか右サブツリーかを4つに分けて議論し,再帰と同様にここでは4つのケースを削除する図である.

void _SearchTreeRemove_ByLoop(SearchTreeNode** proot,SearchTreeType key)
{
  if( proot == NULL  )
    return;
  if( *proot == NULL )
    return;
  SearchTreeNode* root = *proot;
  SearchTreeNode* pre_root = NULL;
    //         
  while(root)
  {
    if(root->key > key)
    {
      pre_root = root;
      root = root->lchild;
    }
    else if(root->key < key)
    {
      pre_root = root;
      root = root->rchild;
    }
    else if(root->key == key)
    {
      break;
    }
  }
    //           
  if(root == NULL)
  {
    return;
  }
  //            
  if(root == *proot)
  {
    free(*proot);
    *proot = NULL;
    return;
  }
  //                
  if(root->lchild == NULL && root->rchild == NULL)
  {
    //                        
    if(pre_root->key > root->key)
    {
      pre_root->lchild = NULL;
    }
    else 
    {
      pre_root->rchild = NULL;
    }
    free(root);
    root = NULL;
  }
    //             
  else if(root->lchild != NULL && root->rchild == NULL)
  {
      //                        
    if(pre_root->key > root->key)
    {
      pre_root->lchild = root->lchild;
    }
    else 
    {
      pre_root->rchild = root->lchild;
    }
    free(root);
    root = NULL;
  }
    //      
  else if(root->rchild != NULL && root->lchild == NULL)
  {
    if(pre_root->key > root->key)
    {
      pre_root->lchild = root->rchild;
    }
    else 
    {
      pre_root->rchild = root->rchild;
    }
    free(root);
    root = NULL;
  }
  else if(root->rchild != NULL && root->lchild != NULL)
  {
    //          ,          
    SearchTreeNode* max = root->lchild;
    SearchTreeNode* pre_max = NULL;
    while(max->rchild)
    {
      pre_max = max;
      max = max->rchild;
    }
    root->key = max->key;
    //       
    if(pre_max == NULL)
    {
     free(root->lchild);
     root->lchild = NULL;
    }
    else 
    {
      //        ,    
      free(pre_max->rchild);
      pre_max->rchild = NULL;
    }
  }
}