二叉の木を検索する基本的な操作(再帰と非再帰)

ダブルツリーを検索:
    二叉樹の探索では、ルートノードは、すべての左サブツリーノードの値よりも大きい.すべての右サブツリーノードの値よりも小さい.
このブログの基本的な操作は以下の通りです.
1.再帰的および非再帰的な挿入
2.再帰的と非再帰的な削除
3.再帰的検索と非再帰的検索

#include
#include
typedef char SearchTreeType; 

typedef struct SearchTreeNode { 
    SearchTreeType data; 
    struct SearchTreeNode* lchild; 
    struct SearchTreeNode* rchild; 
} SearchTreeNode; 

 
初期化:

void SearchTreeInit(SearchTreeNode** root){
    if(root == NULL){
        return;//    
    }
    *root = NULL;
    return;
}

ここでは、ルートノードを削除するなどの操作があります.
 
作成ノード:
 

SearchTreeNode* CreateSearchNode(SearchTreeType value){
    SearchTreeNode* new_node = (SearchTreeNode*)malloc(sizeof(SearchTreeNode));
    new_node->data = value;
    new_node->rchild = NULL;
    new_node->lchild = NULL;
    return new_node;
}

再帰的に挿入:

//    
void SearchTreeInsert(SearchTreeNode** root,SearchTreeType value){
    if(root == NULL){
        return;
    }
    if(*root == NULL){
        //  ，          root       
        SearchTreeNode* new_node = CreateSearchNode(value);
        *root = new_node;
        return;
    }
    //          
    SearchTreeNode* cur = *root;
    if (valuedata){
        // 
        SearchTreeInsert(&cur->lchild,value);
    }else if (value>cur->data){
        SearchTreeInsert(&cur->rchild,value);
    }else{
        //     ，        
        //1.               
        //2.    （    ）
        //3.             ，         
        //       
        return;
    }
    return;
}

 
 
 
再帰的でない挿入:

//     
void SearchTreeInsertByLoop(SearchTreeNode** root,SearchTreeType value)
{
    if(root == NULL)
    {
        return;
    }
    SearchTreeNode* new_node = CreateSearchNode(value);
    if(*root == NULL)
    {
        *root = new_node;
        return;
    }
    SearchTreeNode* cur = *root;
    while(1)
    {
        if(cur->rchild == NULL && value > cur->data)
        {
            cur->rchild = new_node;
            break;
        }
        if(value < cur->data)
        {
            cur = cur->lchild;
        }
        else if(value > cur->data)
        {
            cur = cur->rchild;
        }
        else
        {
            DestroySrearNode(new_node);
            break;
        }
    }
}

 
 
 
再帰的に削除:

//    
void SearchTreeRemove(SearchTreeNode** root,SearchTreeType key)
{
    //1.          ，    
    //2.          ，              ，    
    //3.             ，
    //              ，    
    //4.************     ，**********
    //5，     
    if(root == NULL)
    {
        return;
    }
    if(*root == NULL)
    {
        return;
    }
    SearchTreeNode* proot = *root;
    if(key < proot->data)
    {
        SearchTreeRemove(&proot->lchild,key);
        return;
    }
    else if(key > proot->data)
    {
        SearchTreeRemove(&proot->rchild,key);
        return;
    }
    else//        
    {
        SearchTreeNode* to_remove = proot;
        //     
        if(proot->lchild == NULL && proot->rchild == NULL)
        {
            //    
            *root = NULL;
            DestroySrearNode(to_remove);
            return;
        }
        else if(proot->lchild != NULL && proot->rchild == NULL)
        {
            //     
            *root = to_remove->lchild;
            DestroySrearNode(to_remove);
            return;
        }
        else if(proot->lchild == NULL && proot->rchild != NULL)
        {
            //     
            *root = to_remove->rchild;
            DestroySrearNode(to_remove);
            return;
        }
        else
        {
            SearchTreeNode* min = to_remove->rchild;
            while(min->lchild != NULL)
            {
                min = min->lchild;
            }
            //min            
            to_remove->data = min->data;
            SearchTreeRemove(&to_remove->lchild,min->data);
            return;
        }
    }
}

 
 
 
非再帰的削除:

//     
void SearchTreeRemoveByLoop(SearchTreeNode** root,SearchTreeType key)
{
    if(root == NULL)
    {
        return;
    }
    if(*root == NULL)
    {
        return;
    }
    SearchTreeNode* cur = *root;
    SearchTreeNode* pre = NULL;
    while(1)
    {
        if(cur->data == key)
        {
            break;
        }
        else if(cur->data > key)
        {
            pre = cur;
            cur = cur->lchild;
        }
        else if(cur->data < key)
        {
            pre = cur;
            cur = cur->rchild;
        }
    }
    //               
    //a.            
    if(cur->lchild == NULL && cur->rchild == NULL)
    {
        if(cur == *root)
        {
            *root = NULL;
        }
        else
        {
            if(cur == pre->rchild)
            {
                pre->rchild = NULL;
            }
            else if(cur == pre->lchild)
            {
                pre->lchild = NULL; 
            }
        }
        DestroySrearNode(cur);
    }
    //b.         
    else if(cur->lchild != NULL && cur->rchild == NULL)
{
    if(cur == *root)
    {
        *root = cur->lchild;
    }
    else
    {
        if(cur = pre->lchild)
        {
            pre->lchild = cur->lchild;
        }
        else if(cur = pre->rchild)
        {
            pre->rchild = cur->lchild;
        }
    }
    DestroySrearNode(cur);
}
//     
else if(cur->lchild == NULL && cur->rchild != NULL)
{
    if(cur == (*root))
    {
        *root = NULL;
    }
    else
    {
        if(cur = pre->lchild)
        {
            pre->lchild = cur->rchild;
        }
        else if(cur = pre->rchild)
        {
            pre->rchild = cur->rchild;
        }
    }
    DestroySrearNode(cur);
}
//        
else
{
    if(cur->lchild != NULL && cur->rchild != NULL)
    {
        if(cur == (*root))
        {
            *root = NULL;
        }
        SearchTreeNode* min = cur->lchild;
        SearchTreeNode* min_pre = cur;
        while(min->lchild != NULL)
        {
            min_pre = min;
            min = min->lchild;
        }
        cur->data = min->data;
        if(min == cur->lchild)
        {
            cur->rchild = min->rchild;
        }
        else
        {
            cur->lchild = min->rchild;
        }
        DestroySrearNode(min);
    }
}
}

 
 
 
再帰的に検索:

//    
SearchTreeNode* SearchTreeFind(SearchTreeNode* root,SearchTreeType to_find)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(root->data == to_find)
    {
        return root;
    }
    else if(to_find < root->data)
    {
        return SearchTreeFind(root->lchild,to_find);
    }
    else
    {
        return SearchTreeFind(root->rchild,to_find);
    }
}

 
 
 
再帰的でない検索:

//     
SearchTreeNode* SearchTreeFindByLoop(SearchTreeNode* root,SearchTreeType to_find)
{
    if(root == NULL)
    {
        return NULL;
    }
    SearchTreeNode* cur = root;
    while(1)
    {
        if(cur == NULL)
        {
            break;
        }
        if(to_find < cur->data)
        {
            cur = cur->lchild;
        }
        else if(to_find > cur->data)
        {
            cur = cur->rchild;
        }
        else
        {
            return cur;
        }
    }
    return NULL;
}