c - C 再帰を使用した二分探索木事前順序トラバーサル

Question

関数で渡される名前を C のバイナリ検索ツリーで検索する関数に取り組んでいます。ただし、トラバーサルが子のない一番左のノードに到達したときに再帰が単純に終了しないように、ループをフォーマットする方法にこだわっています。トラバーサルは事前注文する必要があります (自分自身、次に左の子供、次に右の子供を訪問します)。

私の検索機能は次のとおりです。

tnode *bst_find_by_name(tnode *ptr, const char *nom){

    if(ptr != NULL){
        if(strcmp(ptr->name, nom) == 0){
            return ptr;
        }
        if(ptr->left != NULL){
            return bst_find_by_name(ptr->left, nom);
        }
        if(ptr->right != NULL){
            return bst_find_by_name(ptr->right, nom);
        }
    }

    return NULL;


}

ご覧のとおり、現時点では、関数に渡された文字列と一致しない一番左のノードに到達すると、単純に NULL が返されます。ツリー内で一致が見つからない場合は NULL を返さなければなりませんが、同時に、ツリー内のすべてのノードを検索する機会が得られる前に NULL を返したくないのです。何か案は？

Answer 1

戻り値を保持する一時変数を作成します。bst_find_by_nameNULL が返された場合は NULL 以外が返されたかどうかを確認し、ツリーのチェックを続けます。

次のようなもの。

tnode *ret = NULL;
if(ptr->left != NULL){
    ret = bst_find_by_name(ptr->left, nom);
}
if(ret == NULL && ptr->right != NULL){
    ret = bst_find_by_name(ptr->right, nom);
}
return ret;