如何在树中搜索节点并返回它?

我正在尝试在二叉树中搜索节点并返回以防它存在,否则返回null。 顺便说一句,节点类有一个方法名称()返回一个字符串及其名称…到目前为止我所拥有的是:

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; } 

它是否正确??

如果结果不为null,则需要确保对搜索的递归调用返回。

像这样的东西应该工作……

 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; } } 
 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; } 

如果在node.left或node.right中找到它,你应该返回一些东西,所以else块应该是这样的:

  else{ Node temp = search(name, node.left); if (temp != null) return temp; temp = search(name, node.right); if (temp != null) return temp; } 

你不会对递归调用的结果做任何事情

 Node res = search(name, node.left); if(res!=null)return res; res = search(name, node.right); if(res!=null)return res; 

这可能会更好:

 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; 
 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; } 

实际上,尽量避免递归。 如果您有大树结构,您将收到堆栈溢出错误。 而不是这个你可以使用一个列表:

 private Node search(String name, Node node){ List l = new ArrayList(); l.add(node); While(!l.isEmpty()){ if (l.get(0).name().equals(name)) return l.get(0); else { l.add(l.get(0).left); l.add(l.get(0).right); l.remove(0); } } return null; } 

由于语言对于这个问题并不重要,因此这里是C#中预先遍历遍历的内容:

 public static Node FindNode(Node n, int nodeValue) { if (n == null) return null; if (n.Value == nodeValue) return n; return FindNode(n.Left, nodeValue) ?? FindNode(n.Right, nodeValue); } 
 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; }