Est-ce qu'un arbre binaire est contenu dans un autre arbre binaire - C

Question

Donc, j'ai juste eu une interview que je suis confiant que j'ai foiré royalement. J'ai eu un tas de questions lancées sur moi et n'ai pas eu assez de temps pour répondre à la dernière. Après avoir corrigé toutes les questions initiales, on m'a demandé d'écrire une fonction qui déterminerait si un arbre binaire b est contenu dans un autre arbre binaire a. Je codé la question avant que correctement, dans lequel il m'a demandé d'écrire une fonction pour déterminer si deux arbres sont égaux:

int sameTree(struct node *a, struct node *b){ 
//both empty = TRUE 
if(a == NULL && b == NULL) 
    return TRUE; 
//both not empty, compare them 
else if(a != NULL && b != NULL){ 
    return(
    a->data == b->data && 
    sameTree(a->left, b->left) && 
    sameTree(a->right, b->right) 
    ); 
} 
//one empty, one not = FALSE 
else 
    return FALSE; 

}

Ugh. Juste pour clarifier ma conscience, encore une fois comment détermineriez-vous si l'arbre b est à l'intérieur de l'arbre a?

Merci pour toute aide les gars.

Answer 1

Cela suppose que vous voulez le même arbre avec la même structure, contient en a:

D'une part, si b est nul et a n'est pas, un contient b (vous devriez vérifier que dans votre dernière else) .
En second lieu, ce ne sont pas des arbres binaires de recherche (non triés), afin de vérifier si b est à l'intérieur d'un, vous devriez également traverser un (en supposant renommer la fonction):

int containsTree(struct node *a, struct node *b){ 
//both empty = TRUE 
if(a == NULL && b == NULL) 
     return TRUE; 
//both not empty, compare them 

else if(a != NULL && b != NULL){ 
    return(
     // sameTree should be changed to allow nulls, as below 
     sameTree(a, b) 
     // check recursively 
     || containsTree(a->left, b) 
     || containsTree(a->right, b) 
    ); 
//one empty, one not = FALSE 
else 
    return B == NULL; 

Answer 2

Pour vérifier si l'arbre A est contenu tel qu'il est dans l'arbre B, trouver le noeud C dans B tel que C.data == A.data. Si ce noeud n'existe pas, A n'est pas contenu dans B. Si C existe, vérifiez si et C sont égaux en utilisant une fonction sameTree modifiée - une qui ignore les discordances entre les enfants NULL des enfants A et non NULL de C (retourner vrai si A.left/right est nul).

Merci @Kobi pour la correction.

Answer 3

int in(struct node* outer, struct node* inner){ 
    if(inner == null){ 
     return true; // say every tree contains the empty tree 
    } else if(outer == null){ 
     return false; 
    } else if(same(outer, inner)){ 
     return true; 
    } else return in(outer->left, inner) || in(outer->right, inner); 
} 

Il ne faut pas utiliser le sameTree OP mais cette fonction:

int same(struct node* outer, struct node* inner){ 
    return !inner || outer && outer->data == inner->data && same(outer->left, inner->left) && same(outer->right, inner->right); 
} 

Ou, plus verbeux,

int same(struct node* outer, struct node* inner){ 
    if(inner == null){ 
     return true; 
    } else if(outer == null){ 
     return false; 
    } else if(outer->data == inner->data){ 
     return same(outer->left, inner->left) && same(outer->right, inner->right); 
    } else return false; 
}