J'essaye d'écrire une fonction pour rechercher une valeur dans une arborescence de recherche binaire et retourner le TreeNode avec la valeur.Binary Search Tree Questions
struct TreeNode
{
int value;
struct TreeNode *pLeft, *pRight;
};
TreeNode* SearchTree(int query);
(Pour tout noeud: this->pLeft contient des noeuds moins l'this->value, this->pRight contient des noeuds de plus grandes alors this->value)
il serait quelque chose le long des lignes de:
treenode* SearchTree(int query, treenode* node)
{
if(node == NULL)
return NULL;
else if(query == node->value)
return node;
else if(query < node->value)
return SearchTree(query, node->pLeft);
else if(query > node->value)
return SearchTree(query, node->pRight);
else
return NULL;
}
si le noeud qui vous êtes à, a la valeur de ce que vous recherchez, renvoyez l'adresse du nœud. Si la valeur du nœud actuel est inférieure à ce que vous recherchez, descendez la feuille de droite, si la valeur actuelle du nœud a plus que ce que vous recherchez, descendez la feuille de gauche. Restez récursif jusqu'à ce que vous atteigniez une feuille vide, en fonction de votre implémentation de la fin de l'arbre. Mais c'est l'idée générale.
Deux erreurs élémentaires ici: 1. Votre fonction n'a pas de critère de terminaison, dans le cas où la requête n'est pas dans l'arborescence. (Je sais que vous le mentionnez dans votre commentaire, mais c'est plus important que cela - cela devrait figurer sur le code.) 2. Vous ne renvoyez pas une valeur. – TonyK
TonyK, ok J'ai changé le code pour vérifier les critères de terminaison, il pourrait avoir sa propre terminaison en quelque sorte, je suppose juste maintenant que tous ses nœuds feuilles seront alors NULL. question demandée de retourner le TreeNode avec la valeur, pas la valeur elle-même. – han
J'ai un peu simplifié ce code. Il manquait des instructions 'return' et faisait référence à' this' dans des endroits où cela aurait dû être 'node'. – asveikau
Vous résolvez ceci en utilisant la récursivité.
Vous avez besoin d'une étape de terminaison.
Vous aurez également besoin de l'étape récursive qui vérifie un nœud d'arbre et s'appelle lui-même.
Je vous suggère d'utiliser NULL comme la valeur de retour quand il ne se trouve pas.
D'accord. Alors qu'avez-vous si loin? –
Le code que j'ai déjà est déjà listé. –
S'il vous plaît ne vous attendez pas à ce que les autres fassent vos devoirs pour vous. Si vous êtes coincé avec quelque chose, les gens ici pourraient vous donner quelques conseils afin que vous puissiez progresser dans votre travail. Mais, avant cela, vous devez montrer que vous savez ce que vous faites et où votre problème est. – Pirooz