J'essaie de terminer une méthode qui prend une valeur, je dois trouver récursivement les ancêtres d'un nœud avec une valeur correspondante dans un arbre binaire, jusqu'à présent, je rencontre un peu de problèmes avec la partie récursive , voici la classe IM travaillant avec: et voici ce que j'ai jusqu'à présent avec mes ancêtres Méthode: je suis bloqué sur la façon dont Je peux utiliser la récursivité pour vérifier la valeur suivante dans l'arborescence avec ma variable TEMP si elle est simplement définie sur Rooter à chaque fois. S'il y a une autre façon im toutes les oreilles!
3 Réponses :
Au lieu de faire une récursion, vous pouvez simplement installer Temp = root comme vous l'avez fait, puis utilisez une boucle tandis que:
while ( temp->left && temp->right && temp->info != item )
{
if ( temp->info > item )
{
// your ancestor stuff
temp = temp->left;
}
else if ( temp->info < item )
{
// your ancestor stuff
temp = temp->right;
}
}
En fait, je l'avais comme ça avant, mais la mise en œuvre doit être récursive!
Je ne vois aucune raison d'utiliser une récursion si vous avez déjà résolu le problème (un exercice éducatif?). De toute façon, vous pouvez avoir votre fonction ancêtre en tant qu'argument et faire la même chose si / sinon si des trucs à l'intérieur mais au lieu de faire temp = Temp-> à gauche, vous pouvez appeler l'ancêtre (Temp-> à gauche) et utiliser le type de retour à Concaténer votre chaîne de sortie des appels récursifs de gauche ANS
YEA HAHA C'est un exercice éducatif, malheureusement, je ne suis pas autorisé à modifier les paramètres de la méthode ou d'autre que je ferais cela.
xD. Je vois une autre alternative: Si ItemType est un entier, vous pouvez réserver des bits pour encoder le chemin du nœud de la racine. 1 = gauche, 0 = droite et vous pouvez également encoder la profondeur de la récursion pour savoir combien de bits sont lisibles. Cela nécessite de connaître la profondeur maximale possible 2 ^ N afin de le représenter avec n bits + n bits pour le chemin de nœud gauche / droit
ItemType est de type chaîne, merci pour cette explication très détaillée!
S'il y a une autre façon im toutes les oreilles! p>
Considérez: p>
a) Passez un "Vector de Treenodes" comme deuxième paramètre dans votre méthode des ancêtres (). p>
b) pendant la recherche récursive (j'ai utilisé la profondeur d'abord), utilisez push_back fort> dans le vecteur pour capturer les ancêtres visités (noeud *) pendant la recherche, p> c) et lorsque la valeur est trouvée, renvoyez l'ancêtre d'intérêt. P>
D) Lorsqu'il n'est pas trouvé (dans la branche actuelle), utilisez pop_back fort> pendant la "désignation" pour supprimer le (s) noeud ancêtre indésirable. p>
J'ai utilisé la technique pour trouver les nœuds qui résonnent à une cible. P>
Exemple de sortie: (recherche des nœuds qui somme à -5) p>
// target-sum-search int Node_t::sumSearch(const int targetSum, NVec_t& nodeLog) { int reportCount = 0; // diag only std::cout << " Node_t::sumSearch() " << m_payLoad << std::endl; // CAPTURE visit to log nodeLog.push_back(this); // trace node route (depth-first-search style) if(m_left) { reportCount += m_left->sumSearch(targetSum, nodeLog); // RECURSE } { size_t startLvl = nodeLog[0]->m_lvl; // used in report int accumulateSum = 0; for (size_t i = 0; i < nodeLog.size(); ++i) accumulateSum += nodeLog[i]->m_payLoad; if (targetSum == accumulateSum) { std::stringstream reportLabelSS; reportLabelSS << "\n @ level " << startLvl << ":"; std::cout << showNVec(nodeLog, reportLabelSS.str()); reportCount += 1; } } if(m_right) { reportCount += m_right->sumSearch(targetSum, nodeLog); // RECURSE } // REMOVE this node visit from log nodeLog.pop_back(); // removes last nodeLog element // DE-CURSE return(reportCount); // report count }
Malheureusement, je ne peux pas modifier les paramètres de la méthode, merci pour cette rédaction très détaillée!
Je suis bloqué sur la manière dont je peux utiliser la récursivité pour vérifier la valeur suivante dans l'arborescence avec ma variable Temp si elle est définie sur root chaque fois.
C'est une erreur courante avec une solution simple. (Mais peut-être pas si vous ne pouvez pas ajouter une méthode)
essentiellement, vous essayez de faire trop de choses dans une seule fonction.
La solution simple consiste à diviser votre courant Fonctionne en 2 fonctions,
a), qui gère l'initialisation de l'endroit où commencer la recherche, qui n'est pas récursif,
b) et une autre qui effectue la récursivité.
J'espère que ce qui suit fournit suffisamment d'indice pour vous (car je ne suis pas pratiqué avec des modèles)