如何跟踪二叉搜索树有序方法中的先前节点？

Question

我的问题很简单。我正在使用 Java 进行二叉搜索树中序遍历（递归），不知何故我需要比较我遇到的最后一个和当前一个之间的节点值，看看整棵树是否是是否为二叉搜索树。我在下面使用了这样的签名：

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

在这个方法中，p表示我正在处理的当前节点，q表示我处理的最后一个节点。我在编写方法时遇到问题。因此，请分享您的知识。

Answer 1

我认为您不需要将 TreeNode 列表作为此辅助方法的参数，因为当您传入根节点时，它已经包含所有其他 TreeNode。这是一种确定二叉树顺序是否正确的方法。（首先将根节点传递给 public 辅助方法）：

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

这是假设您使用的树节点 class 与此类似：

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

为了检查 Tree 是 BST 还是 Not 我们可以进行中序遍历。在进行中序遍历时，我们可以跟踪先前访问过的节点。如果当前访问的节点的值小于之前的值，则树不是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;
}

}

TreeNode 是：

public class TreeNode {

public int value;

public TreeNode left;

public TreeNode right;

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

如何跟踪二叉搜索树有序方法中的先前节点？

How can I keep track of the prior node in a binary search tree in-order method?

java

tree

binary-tree

binary-search-tree