I'm trying to search for a nod开发者_开发技巧e in a binary tree and return in case it's there, otherwise, return null. By the way, the node class has a method name() that return a string with it's name...What I have so far is:
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;
}
Is this correct??
You need to make sure your recursive calls to search return if the result isn't null.
Something like this should work...
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;
}
Since language doesn't matter much for this question, here's what it looks in C# with pre-order traversal:
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);
}
you should return something if it is found in node.left or node.right so the else block should be something like that:
else{
Node temp = search(name, node.left);
if (temp != null) return temp;
temp = search(name, node.right);
if (temp != null) return temp;
}
you don't do anything with the result of the recursive calls
Node res = search(name, node.left);
if(res!=null)return res;
res = search(name, node.right);
if(res!=null)return res;
This might be better:
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;
}
Actually, try to avoid recursivity. In case you have big tree structure you will get stack overflow error. Instead of this you can use a list:
private Node search(String name, Node node){
List<Node> l = new ArrayList<Node>();
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;
}
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
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);
}
For C++ guys:
//search in a binary tree | O(n)
TreeNode* searchBST(TreeNode* root, int val) {
if(!root) return root;
if(root->val == val) return root;
TreeNode* temp = searchBST(root->left, val);
if(!temp){
temp = searchBST(root->right, val);
}
return temp;
}
//search in a BST | O(logn)
TreeNode* searchBST(TreeNode* root, int val) {
if(!root) return root;
if(root->val == val) return root;
if(val < root->val) return searchBST(root->left, val);
return searchBST(root->right, val);
}
精彩评论