리 팩터링 코드 이진 트리가 BST인지 찾기

Question

주어진 트리가 BST인지 찾기위한 코드를 작성했습니다. 하지만 리팩토링에 도움이 필요합니다. 내가 찾고있는 것들 중 일부는 다음과 같습니다

더 나은 방법 이름

또한

을

결합 leftTreeMax 및 RighTreeMin 방법 (마틴 파울러에 의해 제안)

1. 는 임시 변수의 없애 버리는, 나는 사람들이 가지고있는 다른 모든 리팩터링 아이디어에 감사 할 것입니다.

   package com.cc.bst; 
   
   import com.cc.queue.Queue; 
   import com.cc.trees.BinaryTreeNode; 
   
   public class IsBinaryTreeBST { 
   
   public static boolean binaryTreeBST (BinaryTreeNode root) { 
   
       if (root == null) { 
        return false; 
       } 
       int maxVal = leftTreeMax(root.getLeft()); 
       int minVal = rightTreeMin(root.getRight()); 
       int rootVal = root.getData(); 
   
       if (maxVal == 0 || minVal == 0) { 
        return false; 
       } 
   
       if (rootVal > maxVal && rootVal < minVal) { 
        return true; 
       } 
   
       return false; 
   
   } 
   
   private static int leftTreeMax (BinaryTreeNode node) { 
   
       if (node == null) { 
        return 0; 
       } 
       Queue nodeQueue = new Queue(); 
       nodeQueue.enqueue(node); 
       int maxValue = node.getData(); 
   
       while (!nodeQueue.isEmpty()) { 
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();   
        BinaryTreeNode left = tempNode.getLeft(); 
        BinaryTreeNode right = tempNode.getRight(); 
   
        if (left != null) { 
         if (left.getData() > tempNode.getData()) { 
          return 0; 
         } 
         nodeQueue.enqueue(left); 
        } 
        if (right != null) { 
         if (tempNode.getData() > right.getData()) { 
          return 0; 
         } 
         nodeQueue.enqueue(right); 
        } 
        if (tempNode.getData() > maxValue) { 
         maxValue = tempNode.getData(); 
        }   
       }  
       System.out.println("---------- maxVal -------->" + maxValue); 
       return maxValue; 
   } 
   
   private static int rightTreeMin(BinaryTreeNode node) { 
   
       if (node == null) { 
        return 0; 
       } 
       Queue nodeQueue = new Queue(); 
       nodeQueue.enqueue(node); 
       int minValue = node.getData(); 
   
       while (!nodeQueue.isEmpty()) { 
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();   
        BinaryTreeNode left = tempNode.getLeft(); 
        BinaryTreeNode right = tempNode.getRight(); 
        System.out.println("---------- tempNode -------->" + tempNode.getData()); 
   
        if (left != null) { 
         System.out.println("---------- left -------->" + left.getData()); 
   
         if (left.getData() > tempNode.getData()) { 
          return 0; 
         } 
         nodeQueue.enqueue(left);     
        } 
        if (right != null) { 
         if (tempNode.getData() > right.getData()) { 
          return 0; 
         } 
         System.out.println("---------- right -------->" + right.getData()); 
   
         nodeQueue.enqueue(right);    
        }   
        if (tempNode.getData() < minValue) { 
         minValue = tempNode.getData(); 
        } 
       }  
       System.out.println("---------- minVal -------->" + minValue); 
   
       return minValue; 
        } 
   } 
   

Answer 1

솔직히 말해서 코드가 너무 복잡합니다. 개선의 필요성을 알기가 어렵습니다. 다시 작성하는 것이 더 간단 해 보입니다. 이런 식으로 생각 :

우리는 (위키 백과에서 찍은), 3 개 규정을 충족해야합니다

이

1. 노드의 왼쪽 하위 트리 만 포함하는 노드의 키보다 작은 키 노드.
2. 노드의 오른쪽 하위 트리에는 노드의 키보다 크거나 같은 키가있는 노드 만 포함됩니다.
3. 왼쪽 및 오른쪽 하위 트리는 모두 이진 검색 트리 여야합니다.

따라서 규칙 3은 각 하위 트리가 상위 트리와 동일한 규칙을 가져야하므로 재귀가 순서대로된다는 것을 나타냅니다.

이

checkBST(node,min,max) { 
    if(node == NULL) 
     return true 
    if(node.value < min || node.value >= max) 
     return false 
    return checkBST(left,min,node.value) && checkBST(right,node.value,max) 
} 

checkBST(root,-infinity,+infinity) 

는이 경계가 부모에 의해 수신되고 그 값에 대한 경계를 유지하는 각 하위 트리입니다 무슨 일을하는이 방법은, 이제 할 수 있습니다 :

왜 이런 일을하지 왼쪽 하위 트리가 부모보다 작을 필요가 있다고 가정하면 상위 노드가이 하위 트리가 될 수있는 최대 값이며 상위 하위 트리가 상위 노드와 같거나 같아야합니다.

이 알고리즘은 가장 좋은 시간 복잡성은 아니지만 작성하고 이해하는 것이 가장 간단합니다.