检查二叉树是否是二叉搜索树的伪代码-不确定递归

Question

我需要编写伪代码来检查有效的二叉树是否是搜索二叉树。

我创建了一个数组来保存树的顺序值。如果顺序值是降序的，这意味着它确实是BST。然而，我对INOVERAR方法中的递归有一些问题。

我需要更新数组的索引，以便按照值在树上的顺序将其提交给数组。

我不确定在递归过程中索引是否真的得到了正确更新。。到底是不是？如果你发现问题，能帮我解决吗？谢谢

伪代码

第一功能

IsBST（节点）

大小← 树化（节点）

创建新数组TreeArr of size单元格数

指数← 0

评论很少：现在我们使用的IN_ORDER程序有一个小的变化，我调用了新版本的程序：InOrderArr InOrderArr的伪代码描述如下IsBST

InOrderArr（节点、TreeArr、索引）

对于我来说，从1号到1号都可以

如果不是（特雷尔[i]

返回真值

第二个功能

InOrder（节点、数组、索引）如果node=NULL，则返回

别的

顺序（node.left、数组、索引）

索引node.key

指数← 指标1

InOrderArr（node.right，数组，索引）

回来

Answer 1

你的代码通常是正确的。只有三个音符。

>

代码的正确性取决于实现，特别是index处理的方式。许多编程语言通过值将参数传递给子例程。这意味着子例程接收值的副本，对参数所做的修改对原始值没有影响。因此，在执行InOrderArr（node.left， Array， index）期间递增index不会影响treeArr[index]=node.key使用的位置。因此，只有最右边的路径会存储在数组中。
为了避免这种情况，您必须确保index通过引用传递，以便被调用者完成的增量会推进调用者稍后使用的位置。

BST的定义通常是这样的：节点的左子树包含的密钥小于该节点的密钥，而右子树包含的节点具有更大的密钥——请参阅维基百科关于BST的文章。然后，索引遍历按升序检索密钥。你为什么期望降序？

删除数组并递归测试BST的定义条件可能会更有效
每当我们跟随左链接时，我们都希望得到比当前键小的键。每当我们点击右键链接时，我们都希望键比当前键大。所以对于大多数子树，都有一些键值的间隔，由一些祖先节点的键定义。只需跟踪这些密钥，测试密钥是否在当前有效间隔内。确保在letfmost路径上处理“未定义左端”条件，在树的最右侧路径上处理“未定义右端”条件。在根节点上还没有祖先，所以根本不测试根键（任何值都可以）。

编辑

C代码草案：

    // Test a node against its closest left-side and right-side ancestors
    boolean isNodeBST(NODE *lt, NODE *node, NODE *rt)
    {
        if(node == NULL)
            return true;
        if(lt != NULL && node->key < lt->key)
            return false;
        if(rt != NULL && node->key > rt->key)
            return false;

        return
            isNodeBST(lt, node->left, node) &&
            isNodeBST(node, node->right, rt);
    }

    boolean isTreeBST(TREE *tree)
    {
       return isNodeBST( NULL, tree->root, NULL);
    }