Обход дерева для поиска узла

Question

Я ищу в дереве, чтобы найти переданное значение. К сожалению, это не работает. Я начал отлаживать его с помощью отпечатков, и что странно, он действительно находит значение, но пропускает оператор return.

    /**
  * Returns the node with the passed value
  */
 private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node)
 {  
  if(node == null) 
  {
   return null;
  }

  if(c.equals((Comparable)node.getValue()))
  {
   System.out.println("Here");
   return node;
  }
  else
  {
   if(node.getLeft() != null)
   {
    System.out.println("left");
    searchNodeBeingDeleted(c, node.getLeft());
   }
   if(node.getRight() != null)
   {
    System.out.println("right");
    searchNodeBeingDeleted(c, node.getRight());
   }
  }
  return null; //i think this gives me my null pointer at bottom
 }

Распечатывает результаты следующим образом:

left
left
right
right
Here
right
left
right
left
right
Exception in thread "main" java.lang.NullPointerException
at Program_14.Driver.main(Driver.java:29)

Не знаю, поможет ли это, но вот мое дерево:

     L
   /   \
  D     R
 / \   / \
A   F M   U
 \       / \
  B     T   V

Спасибо за ваше время.

Answer 1

Попробуйте это:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node)
 {  
  if(node == null) 
  {
   return null;
  }

  if(c.equals((Comparable)node.getValue()))
  {
   System.out.println("Here");
   return node;
  }
  else
  {
   if(node.getLeft() != null)
   {
    System.out.println("left");
    TreeNode n = searchNodeBeingDeleted(c, node.getLeft());
    if (n != null) {
      return n;
    }
   }
   if(node.getRight() != null)
   {
    System.out.println("right");
    TreeNode n = searchNodeBeingDeleted(c, node.getRight());
    if (n != null) {
      return n;
    }
   }
  }
  return null; //i think this gives me my null pointer at bottom
 }

Answer 2

Предполагая, что ваше дерево - это дерево двоичного поиска , а не "обычное" двоичное дерево .

Вы должны возвращать свои рекурсивные вызовы и не возвращать null в конце вашего метода.

Примерно так:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node) {
    if(nodle == null) return null;
    int diff = c.compareTo((Comparable)node.getValue());
    if (diff == 0) { // yes, we found a match!
        System.out.println("Here");
        return node;
    }
    else if (diff < 0) { // traverse to the left
        System.out.println("left");
        return searchNodeBeingDeleted(c, node.getLeft());
    }
    else {  // traverse to the right
        System.out.println("right");
        return searchNodeBeingDeleted(c, node.getRight());
    }
}

Answer 3

Вы используете рекурсию в своей функции. «Здесь», которое вы видите, является результатом вызова функции, которая была создана из той же функции. Таким образом, он вернет значение функции 'recuring', на данный момент вы еще не закончили, хотя вы и нашли ответ, вам все равно нужно продолжать распространять его вверх.

Answer 4

Я думаю, что вы должны вернуть значения searchNodeBeingDeleted(c, node.getLeft()) и searchNodeBeingDeleted(c, node.getRight()), а не просто вызывать эти методы.