J'essaie de rechercher un nœud dans un arbre binaire et de retour au cas où il est là, sinon, retourne null. Au fait, la classe de nœud a un nom de méthode () qui renvoie une chaîne avec son nom ... ce que j'ai jusqu'à présent:
private Node search(String name, Node node){
if(node != null){
if(node.name().equals(name)){
return node;
}
else{
search(name, node.left);
search(name, node.right);
}
}
return null;
}
13 Réponses :
Cela pourrait être meilleur:
if(node != null){
if(node.name().equals(name)){
return node;
}
else {
Node tmp = search(name, node.left);
if (tmp != null) { // if we find it at left
return tmp; // we return it
}
// else we return the result of the search in the right node
return search(name, node.right);
}
}
return null;
renvoyer null; À la fin, peut donner un avertissement de compilation (en fonction de la configuration) car c'est un code inaccessible.
Vous avez raison, a raté la grande déclaration si elle est au sommet. mon erreur.
Vous devriez retourner quelque chose s'il est trouvé dans Node.Left ou Node.Right. Donc, le Bloc Block devrait être quelque chose comme ça:
else{
Node temp = search(name, node.left);
if (temp != null) return temp;
temp = search(name, node.right);
if (temp != null) return temp;
}
Un instruction NULL NULL est nécessaire à la fin de sinon Body o gérer le boîtier si la clé n'est pas trouvée.
Vous ne faites rien avec le résultat des appels récursifs
Vous devez vous assurer que vos appels récursifs à la recherche de retour si le résultat n'est pas NULL.
Quelque chose comme ça devrait fonctionner ... P>
private Node search(String name, Node node){
if(node != null){
if(node.name().equals(name)){
return node;
} else {
Node foundNode = search(name, node.left);
if(foundNode == null) {
foundNode = search(name, node.right);
}
return foundNode;
}
} else {
return null;
}
}
Vous avez oublié un point-virgule après le retour de Foundnode;
Fantastique, cela fonctionne comme un charme, mais j'ai trouvé ce fil parce que j'avais des problèmes avec ma propre méthode récursive ... La note de vous assurer que vous renvoyez NULL si le résultat n'est pas sauvé ma journée
Agréable! C'est un peu un bender-esprit mais ça marche un régal!
Boolean FindInBinaryTreeWithRecursion(TreeNode root, int data)
{
Boolean temp;
// base case == emptytree
if (root == null) return false;
else {
if (data == root.getData()) return true;
else { // otherwise recur down tree
temp = FindInBinaryTreeWithRecursion(root.getLeft(), data);
if (temp != true)
return temp;
else
return (FindInBinaryTreeWithRecursion(root.getRight(), data));
}
}
}
public static TreeNode findNodeInTree(TreeNode root, TreeNode nodeToFind) {
if (root == null) {
return null;
}
if (root.data == nodeToFind.data) {
return root;
}
TreeNode found = null;
if (root.left != null) {
found = findNodeInTree(root.left, nodeToFind);
if (found != null) {
return found;
}
}
if (root.right != null) {
found = findNodeInTree(root.right, nodeToFind);
if (found != null) {
return found;
}
}
return null;
}
public Node findNode(Node root, Node nodeToFind) {
Node foundNode = null;
Node traversingNode = root;
if (traversingNode.data == nodeToFind.data) {
foundNode = traversingNode;
return foundNode;
}
if (nodeToFind.data < traversingNode.data
&& null != traversingNode.leftChild) {
findNode(traversingNode.leftChild, nodeToFind);
} else if (nodeToFind.data > traversingNode.data
&& null != traversingNode.rightChild) {
findNode(traversingNode, nodeToFind);
}
return foundNode;
}
En fait, essayez d'éviter la récursivité.
Si vous avez une grande structure d'arborescence, vous obtiendrez une erreur de dépassement de pile.
Au lieu de cela, vous pouvez utiliser une liste:
Étant donné que la langue n'a pas beaucoup d'importance pour cette question, voici ce qu'il ressemble à C # avec une traversée de pré-commande:
public static boolean findElement(Node root, int value) {
if (root != null) {
if (root.data == value) {
return true;
} else {
return findElement(root.left, value) || findElement(root.right, value);
}
}
return false;
}
public TreeNode searchBST(TreeNode root, int val) {
if(root==null || root.val==val) return root;
TreeNode found = (val < root.val) ? searchBST(root.left,val) : searchBST(root.right,val);
return found;
}
View Code on GitHub
Vous devriez ajouter une explication à votre réponse.
private TreeNode findX(TreeNode root, int x) {
if(root == null) return null;
if(root.val == x) return root;
TreeNode left = findX(root.left,x);
TreeNode right = findX(root.right,x);
if(left == null) return right;
return left;
}
Node* search(Node* root,int key){
// If key is found or is NULL
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
Avez-vous essayé de l'exécuter pour voir si les résultats sont corrects? Pourquoi pensez-vous que cela pourrait pas correct?
L'as tu essayé? Faire un cas d'essai est l'une des parties les plus importantes du codage.