BST를 모두 검색하는 재귀 알고리즘이 필요합니다.

Question

BST의 모든 노드를 방문하여 가장 큰 int 값을 찾기위한 알고리즘을 찾으려고하면 BST는 불균형이고 사전 순으로 정렬되지만 int 값이 있습니다. 트리에서 가장 큰 int 값을 찾아야합니다.

내 코드는 다음과 같습니다

private Object Mode(BinaryTreeNode root) { 
    if (root == null) { 
     return null; 
    } 

    Object left = root.getElement(); 
    Object right = root.getElement(); 

    if (root.getLeftChild() != null) { 

     Object leftEle = root.getLeftChild().getElement(); 

     if (left.data < leftEle.data) { 
      left = Mode(root.getLeftChild()); 

     } 
    } 

    if (root.getRightChild() != null) { 

     Object rightEle = root.getRightChild().getElement(); 

     if (right.data < rightEle.data) { 
      right = Mode(root.getRightChild()); 

     } 
    } 

    if(left.data > right.data){ 
     return left; 
    } 

    return right;` 

} 

은 내가 메서드 호출이 다시 스택에서 팝 때 비교가 일어날 알고 있지만 실제로 모든 노드로

Answer 1

을 확인 결국 있는지 확실하지 않습니다 당신의 BST가 데이터별로 정렬되지 않으면 각 노드를 탐색하여 두 노드를 비교해야합니다. 해당 검사를 제거하면 right.data < rightEle.data & left.data < leftEle.data, 검색 공간이 제한됩니다. 나는 아직 코드를 컴파일하지 않았다.

private Object Mode(BinaryTreeNode root) { 
    if (root == null) { 
     return null; 
    } 

    Object left = root.getElement(); 
    Object right = root.getElement(); 

    if (root.getLeftChild() != null) { 

     Object leftEle = root.getLeftChild().getElement();   
     left = Mode(root.getLeftChild());  
    } 

    if (root.getRightChild() != null) {  
     Object rightEle = root.getRightChild().getElement(); 
     right = Mode(root.getRightChild()); 
    } 
    if(left != null){ 
     if(right != null) 
      if(left.data < right.data 
       return right; 
     return left; 

    } 

    return right; 


}