如何在树中搜索节点并返回它?
我正在尝试在二叉树中搜索节点并返回以防它存在,否则返回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; }