Как найти узел в двоичном дереве поиска

Question

Я читал о бинарных деревьях в java. Я нашел этот код:

public BSTNode findNode(Comparable val){ 
     int delta = val.compareTo(value); 
     // the value is less than this.value 
     if(delta < 0){ 
      // if there is a leftChild, return left.findNode(val) 
      // there is no leftChild, so the val does not exist 
      // in the node, so return null 
      return (left!= null)? left.findNode(val): null; 
     } 
     // else if the value is greater than this.value 
     else if (delta > 0){ 
      // if there is a rightChild, then return right.findNode(val) 
      // else, there is no rightChild, return null 
      return (right != null)? right.findNode(val): null; 
     } 
     // else, dela == 0, so we have found the node with that 
     // val, return the node 
     return this; 
    } 

Я не понимаю, как это работает:

return (left!= null)? left.findNode(val): null; 
return (right != null)? right.findNode(val): null; 

Вы можете переписать это по-другому?

Спасибо

Answer 1

OK, переходим шаг за шагом. Прежде всего, я сосредоточусь на самом алгоритме.

class Node<T> { 
    T value; 
    Node left; 
    Node right; 
} 

Вы гарантированно, что все значения к left меньше или равно, чем value и все значения к right имеют больше или равно, чем value. Это упрощает поиск. Если вы ищете элемент val, вы просто сравниваете его с value в текущем Node. Если желаемый элемент равен текущему элементу, вы его нашли. Если он больше, он может быть только в правой части дерева. В противном случае в левой части.

Может случиться так, что элемента здесь нет. Это происходит, если вы видите, что он должен быть слева/справа от текущего узла, но там ничего нет (null).

Так BinaryTreeSearch является:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return search(tree.getRight(), val); 
    } else { 
     return search(tree.getLeft(), val); 
    } 
} 

Но подождите ... это приводит к NPE, если элемент не здесь. Давайте изменим его:

T search(Node tree, T val) { 
    if (tree == null) 
     return null; 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return search(tree.getRight(), val); 
    } else { 
     return search(tree.getLeft(), val); 
    } 
} 

Это можно также переписать следующим образом:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     if (tree.getRight() == null) 
      return null; 
     return search(tree.getRight(), val); 
    } else { 
     if (tree.getLeft() == null) 
      return null; 
     return search(tree.getLeft(), val); 
    } 
} 

Но здесь возникает тройная оператор, сократить и упростить if-else.

result = testCondition ? value1 : value2 

, который так же, как

if (testCondition) { 
    result = value1; 
} else { 
    result = value2; 
} 

Другой условный оператор?, Который можно рассматривать как стенография для если-то-другое заявление (обсуждается в отчетности Flow Control раздел этого урока). Этот оператор также известен как тернарный оператор, поскольку он использует три операнда. В следующем примере этот оператор следует читать как: «Если someCondition является истинным, назначьте значение value1. В противном случае присвойте значение value2."

Таким образом, мы, наконец, получим:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return (tree.getRight() == null) ? null : search(tree.getRight(), val); 
    } else { 
     return (tree.getLeft() == null) ? null : search(tree.getLeft(), val); 
    } 
} 

Answer 2

Они могут быть переписаны как:

if(left != null) { 
    return left.findNode(val); 
} else { 
    return null; 
} 

и

if(right != null) { 
    return right.findNode(val); 
} else { 
    return null; 
} 

Надеется, что это помогает :-).