检查二叉树是否是二叉搜索树的伪代码 - 不确定递归 [英] Pseudo code to check if binary tree is a binary search tree - not sure about the recursion

问题描述

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

I have homeowork to write pseudo code to check if a valid binary tree is a search binary tree.

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

I created an array to hold the in-order values of the tree. if the in-order values are in decreasing order it means it is indeed BST. However I've got some problem with the recursion in the method InOverArr.

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

I need to update the index of the array in order to submit the values to the array in the order they are at the tree.

我不确定在递归过程中索引是否真的正确更新..是不是?如果你看到一些问题，你能帮我解决这个问题吗?非常感谢

I'm not sure the index is really updated properly during the recursion.. is it or not? and if you see some problem can you help me fix this? thanks a lot

伪代码

第一个函数

IsBST(节点)

size ← TreeSize(node)

size ← TreeSize(node)

创建新的数组 TreeArr 的大小单元格数

create new array TreeArr of Size number of cells

索引 ← 0

一些评论:现在我们使用带有小的变化的 IN_ORDER 过程，我称该过程的新版本为:InOrderArrInOrderArr 的伪代码描述如下 IsBST

few comments: now we use the IN_ORDER procedure with a small variation , I called the new version of the procedure: InOrderArr the pseudo code of InOrderArr is described below IsBST

InOrderArr(node, TreeArr, index)

InOrderArr(node, TreeArr, index)

for i from 1 to size-1 do

for i from 1 to size-1 do

如果不是 (TreeArr[i] > TreeArr[i-1]) 返回假

if not (TreeArr[i] > TreeArr[i-1]) return false

返回真

第二个功能

InOrderArr(节点、数组、索引)如果 node = NULL 则返回

InOrderArr (node, Array, index) if node = NULL then return

其他

InOrderArr (node.left, Array, index)

InOrderArr (node.left, Array, index)

treeArr[index] = node.key

treeArr[index] = node.key

索引←索引+1

InOrderArr (node.right, Array, index)

InOrderArr (node.right, Array, index)

返回

推荐答案

您的代码通常是正确的.只有三个音符.

Your code is generally correct. Just three notes.

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

1. The correctness of the code depends on the implementation, specifically on the way of index handling. Many programming languages pass arguments to subroutines by value. That means the subroutine receives a copy of the value and modifications made to the parameter have no effect on the original value. So incrementing index during execution of InOrderArr (node.left, Array, index) would not affect the position used by treeArr[index] = node.key. As a result only the rightmost path would be stored in the array.
   To avoid that you'll have to ensure that index is passed by reference, so that incrementation done by a callee advances the position used later by a caller.

BST 通常定义为节点的左子树包含小于该节点键的键，而右子树包含键更大的节点 – 请参阅维基百科关于 BST.然后中序遍历按升序检索键.为什么你期望降序?

BST is usually defined so that the left subtreee of a node contains keys that are less than that node's key, and the right subtree contains nodes with greater keys – see Wikipedia's article on BST. Then the inorder traversal retrieves keys in ascending order. Why do you expect descending order?

可能删除数组并递归测试BST的定义条件会更有效吗?
每当我们遵循 left 链接时，我们都希望键小于当前键.每当我们遵循 right 链接时，我们都希望密钥大于当前的密钥.所以对于大多数子树来说，有一些键值的间隔，由一些祖先节点的键定义.只需跟踪这些密钥并测试密钥是否在当前有效间隔内.确保处理最左端路径上的未定义左端"条件和树的最右端路径上的无右端"条件.在根节点还没有祖先，所以根本不测试根键(任何值都可以).

Possibly it would be more efficient to drop the array and just recursively test a definition condition of BST?
Whenever we follow a left link we expect keys which are less than the current one. Whenever we follow the right link we expect keys greater the the current one. So for most subtrees there is some interval of keys values, defined by some ancestor nodes' keys. Just track those keys and test whether the key falls inside the current valid interval. Be sure to handle 'no left end defined' condition on the letfmost path and 'no right end' on the rightmost path of the tree. At the root node there's no ancestor yet, so the root key is not tested at all (any value is OK).

编辑

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

这篇关于检查二叉树是否是二叉搜索树的伪代码 - 不确定递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！