如何跟蹤二叉查找樹按順序方法中的先驗節點？

Question

我的問題很簡單。我使用Java來執行二叉搜索樹按順序遍歷（遞歸），並且不知何故我需要比較我遇到的最後一個和當前一個之間的節點值，以查看整棵樹是二叉搜索樹或不。我用這樣的下方簽名：

private void helper(List<TreeNode> list,TreeNode p,TreeNode q) 

在這種方法中，通過p我的意思是我負責的，由q當前節點我的意思是最後一個我處理。我在寫這個方法時遇到了麻煩。所以請分享你的知識。

Answer 1

我不認爲你需要TreeNodes的列表作爲這個幫助器方法的參數，因爲當你傳入根節點時它已經包含了所有其他的TreeNode。這是確定二叉樹是否按正確順序的方法。 （通過將根節點到公共的輔助方法開始）：

public boolean helper(TreeNode root) 
    { 
     if (root.getLeftNode() == null) 
     { 
      if (root.getRightNode() == null) 
       return true; 
      else return helper(root.getRightNode(), root); 
     } 
     //if everything branching from leftNode is in order 
     else if(helper(root.getLeftNode(), root)) 
     { 
      if (root.getRightNode() != null) 
       return helper(root.getRightNode(), root); 
      else return true; 
     } 
     else return false; 
    } 

    private boolean helper(TreeNode currentNode, TreeNode previousNode) 
    { 
     //Test leftNode 
     if (currentNode == previousNode.getLeftNode()) 
     { 
      if (currentNode.getData() > previousNode.getData()) return false; 
      else 
      { 
       if (currentNode.getLeftNode() == null) 
       { 
        if (currentNode.getRightNode() == null) 
         return true; 
        else return helper(currentNode.getRightNode(), currentNode); 
       } 
       //if everything branching from leftNode is in order 
       else if(helper(currentNode.getLeftNode(), currentNode)) 
       { 
        if (currentNode.getRightNode() != null) 
         return helper(currentNode.getRightNode(), currentNode); 
        else return true; 
       } 
       else return false; 
      } 
     } 
     //Test rightNode 
     else 
     { 
      if (currentNode.getData() < previousNode.getData()) return false; 
      else 
      { 
       if (currentNode.getLeftNode() == null) 
       { 
        if (currentNode.getRightNode() == null) 
         return true; 
        else return helper(currentNode.getRightNode(), currentNode); 
       } 
       //if everything branching from leftNode is in order 
       else if(helper(currentNode.getLeftNode(), currentNode)) 
       { 
        if (currentNode.getRightNode() != null) 
         return helper(currentNode.getRightNode(), currentNode); 
        else return true; 
       } 
       else return false; 
      } 
     } 
    } 

這是假設你正在使用類似這樣的一個樹節點類：

public class TreeNode 
{ 
    private TreeNode leftNode; 
    private TreeNode rightNode; 
    private int data; 

    public TreeNode(int data, TreeNode leftNode, TreeNode rightNode) 
    { 
     this.data = data; 
     this.leftNode = leftNode; 
     this.rightNode = rightNode; 
    } 

    public TreeNode getLeftNode() 
    { 
     return leftNode; 
    } 
    public TreeNode getRightNode() 
    { 
     return rightNode; 
    } 
    public int getData() 
    { 
     return data; 
    } 
} 

我敢肯定，這可以寫成更好，更高效，但我希望這至少能讓你走上正確的軌道。

Answer 2

對於檢查樹是BST還是不是我們可以進行遍歷。 在進行有序遍歷時，我們可以跟蹤以前訪問過的節點。如果當前訪問節點的值小於以前的值，那麼樹不是BST。

public class IsBstTest { 

private static TreeNode prevNode; 

public static void main(String[] args) { 
    TreeNode root = new TreeNode(4); 
    root.left = new TreeNode(2); 
    root.right = new TreeNode(5); 
    root.right.left = new TreeNode(6); 
    root.right.right = new TreeNode(7); 

    if (isBst(root)) 
     System.out.println("Is BST"); 
    else 
     System.out.println("Not a BST"); 
} 

public static Boolean isBst(TreeNode root) { 
    if (root != null) { 
     if (!isBst(root.left)) { 
      return false; 
     } 
     if (prevNode != null && root.value <= prevNode.value) { 
      return false; 
     } 
     prevNode = root; 
     return isBst(root.right); 
    } 
    return true; 
} 

}

而且樹節點是：

public class TreeNode { 

public int value; 

public TreeNode left; 

public TreeNode right; 

public TreeNode(int value) { 
    this.value = value; 
} 
}