Suche nach Element im Binärbaum, Funktion liefert immer 0

Question

Ich schrieb die folgende Funktion in C, die 1 zurückgibt, wenn das Element tatsächlich im Binärbaum ist und 0 andernfalls.

int isElementInBinaryTree(BinaryTreeNode *root, int search_item) { 
if(root) { 
    if(search_item == root -> data) return 1; 
    isElementInBinaryTree(root -> left, search_item); 
    isElementInBinaryTree(root -> right, search_item); 
} 

return 0; 
} 

Zuerst gebe ich die Funktion zu sehen, ob die Wurzel ist, wenn es ist, ich mir die Daten an dieser Wurzel und vergleichen Sie es mit dem search_item. Wenn es wahr ist, gebe ich einfach 1 zurück und verlasse es, ansonsten fahre ich mit der Vorbestellung fort. Warum bekomme ich immer eine 0 zurück? Selbst wenn der Artikel im Binärbaum ist?

Answer 1

ändern diese Linien

isElementInBinaryTree(root -> left, search_item); 
isElementInBinaryTree(root -> right, search_item); 

das Ergebnis zurück.

heißt

return isElementInBinaryTree(root -> left, search_item) || isElementInBinaryTree(root -> right, search_item); 

Wenn das Element in der LHS gefunden wird true zurück - sonst wird es RHS versuchen. Beachten Sie die Verwendung von || - Kurzschluss Betreiber

EDIT

Kann diese erhalten in einer return-Anweisung

int isElementInBinaryTree(BinaryTreeNode *root, int search_item) 
{ 
    return root ? (search_item == root -> data || isElementInBinaryTree(root -> left, search_item) || isElementInBinaryTree(root -> right, search_item)) : 0; 
} 

EDIT 2

eine Annahme zu machen, die Sie suchen: ein Element, das verwendet wird, um den Baum mit LHS zu ordnen, der kleiner als und der RHS größer als ist.

sollte der Code aussehen

int isElementInBinaryTree(BinaryTreeNode *root, int search_item) 
{ 
    if(root) { 
     // Assuming that most of the items in the tree are not the search item 
     // best to check first if we need to search LHS or RHS - these 
     // events are more likely than the item being found! 
     if (search_item < root -> data) return isElementInBinaryTree(root -> left, search_item); 
     if (search_item > root -> data) return isElementInBinaryTree(root -> right, search_item); 
     return 1; // We have found it 
    } 

    return 0; 
} 

Answer 2

Sie zu isElementInBinaryTree nicht den Rückgabewert der rekursiven Aufrufe verwenden. Sie müssen das Ergebnis der rekursiven Aufrufe an den obersten Aufruf weitergeben. Wie es jetzt ist, wird es nur 1 zurückgeben, wenn das Zielobjekt im Wurzelknoten ist.

So:

int isElementInBinaryTree(BinaryTreeNode *root, int search_item) 
{ 
    if(root) { 
     if (search_item == root -> data) return 1; 
     if (isElementInBinaryTree(root -> left, search_item)) return 1; 
     if (isElementInBinaryTree(root -> right, search_item)) return 1; 
    } 

    return 0; 
} 

Answer 3

Nicht nur müssen Sie die Werte aus den rekursiven Aufrufen zurückzukehren, sollten Sie auch nur recurse in die Teile des Baumes, die Ihr search_item enthalten.

So vorausgesetzt, der Baum mit niedriger = sortiert bleibt dann funktionieren Sie sollten wie folgt aussehen:

int isElementInBinaryTree(BinaryTreeNode *root, int search_item) 
{ 
    if(root) { 
     if (search_item == root -> data) return 1; 
     else if (search_item < root -> data) return isElementInBinaryTree(root -> left, search_item); 
     else if (search_item > root -> data) return isElementInBinaryTree(root -> right, search_item); 
    } 

    return 0; 
}