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

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

我创建了一个数组来保存树的有序值。如果有序值按降序排列，则意味着它确实是 BST。但是，我在方法 InOverArr 中的递归方面遇到了一些问题。

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

我不确定索引在递归过程中是否真的正确更新..是不是？如果您发现一些问题可以帮我解决吗？多谢

伪代码

第一个功能

IsBST(节点)

大小 ← TreeSize(节点)

创建新数组 TreeArr，其大小为单元格数

索引 ← 0

几点评论： 现在我们使用带有小变化的 IN_ORDER 过程，我将该过程的新版本称为：InOrderArr InOrderArr的伪代码描述如下 IsBST

InOrderArr（节点，TreeArr，索引）

对于我从 1 到 size-1 做

如果不是 (TreeArr[i] > TreeArr[i-1]) 返回 错误的

返回真

第二个功能

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

else

InOrderArr（节点.left，数组，索引）

treeArr[索引] = 节点.key

索引 ← 索引 + 1

InOrderArr（节点.right，数组，索引）

Return

您的代码通常是正确的。只需三个音符。

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

2. BST 通常被定义为使得节点的左子树包含小于该节点的键的键，而右子树包含具有更大键的节点 - 请参阅 Wikipedia 的文章BST http://en.wikipedia.org/wiki/Binary_search_tree。然后中序遍历按升序检索键。为什么你期望降序排列？

3. 删除数组并递归测试 BST 的定义条件可能会更有效吗？
   每当我们遵循一个left链接我们期望密钥小于当前密钥。每当我们遵循right链接我们期望密钥大于当前的密钥。因此，对于大多数子树来说，存在一些由某些祖先节点的键定义的键值间隔。只需跟踪这些键并测试该键是否落在当前有效区间内即可。确保处理树的最左路径上的“未定义左端”条件和最右路径上的“无右端”条件。在根节点处还没有祖先，因此根本没有测试根键（任何值都可以）。

EDIT

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