2016-10-31 4 views
1

자바에서 이진 트리에 대해 읽었습니다.이진 검색 트리에서 노드를 찾는 방법

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

당신은 다른 방법으로 그것을 다시 작성할 수 있습니다 :

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

나는 이것이 어떻게 작동하는지 이해가 안 :이 코드를 발견?

감사

+3

당신은 삼항 조건 연산자 또는 재귀 무엇을 이해하지 못하는 – Eran

+0

양쪽 라인 :?'리턴 (! 왼쪽 = NULL) left.findNode을 (null); right.findNode (val) : null;'어떻게 작동하는지 모르겠다. – Joe

+2

Java 삼항 연산자 : http://alvinalexander.com/java/edu/ pj/pj010018 –

답변

1

OK, 단계별로 나가 보겠습니다. 우선, 알고리즘 자체에 집중할 것입니다.

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

당신은 left에 모든 값이 작거나 value보다 평등하며 right에 모든 값이 크거나 value 같 것을 보장합니다. 이렇게하면 쉽게 검색 할 수 있습니다. 요소 val을 찾고있는 경우 Nodevalue과 비교하면됩니다. 원하는 요소가 현재 요소와 동일하면 찾았습니다. 그것이 더 큰 경우에만 나무의 오른쪽 부분에있을 수 있습니다. 그렇지 않으면 왼쪽에.

요소가 여기에없는 경우가 있습니다. 현재 노드의 왼쪽/오른쪽에 있어야한다는 것을 알았지 만 아무 것도 없습니다 (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 단순화 온다. 제어 흐름 문에서 논의 if-then-else 명령문 (속기로 생각 될 수있다 :

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

또 다른 조건 연산자는 동일하다

result = testCondition ? value1 : value2 

이 단원의 섹션). 이 연산자는 3 개의 피연산자를 사용하기 때문에 3 항 연산자라고도합니다. 다음 예제에서이 연산자는 다음과 같이 읽어야합니다. "someCondition이 true이면 result에 value1 값을 할당하고 그렇지 않으면 result2에 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); 
    } 
} 
0

그들은으로 다시 작성할 수 있습니다 :

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

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

희망이 :-)하는 데 도움이됩니다.

관련 문제