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

问题描述

我有自己的内核写伪代码来检查一个有效的二进制树是一个搜索二叉树。

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

我需要更新数组的索引，以便将值提交到数组中订单他们在树上。

我不知道索引在递归期间是否正确更新..是不是？如果你看到一些问题可以帮我解决这个问题吗？感谢很多

伪代码

strong>第一个功能

IsBST（节点）

←TreeSize（node）

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

index←0

几个注释：
现在我们使用一个小变体的IN_ORDER过程，我调用了新版本的过程：InOrderArr
InOrderArr的伪代码是描述如下IsBST

InOrderArr（node，TreeArr，index）

对于我从1到大小-1

如果没有（TreeArr [i]> TreeArr [i-1]）return
false

return true

第二个功能

InOrderArr（node，Array，index）
如果node = NULL，则返回

else

InOrderArr（node.l eft，Array，index）

treeArr [index] = node.key

index←index + 1

InOrderArr（node.right，Array，index）

返回

< blockquote>

解决方案

你的代码一般是正确的。只需三个笔记。

1. 代码的正确性取决于实现，具体来说就是索引处理。许多编程语言通过值将参数传递给子程序。这意味着子程序接收到该值的副本，并且对该参数进行的修改对原始值没有影响。因此在执行 InOrderArr（node.left，Array，index）期间递增 index 不会影响 treeArr [index] = node.key 。因此，只有最右边的路径将存储在数组中。
   
   为了避免你必须确保通过引用传递 index 所以由被叫者进行的递增提前了呼叫者以后使用的位置。




2. 通常定义BST，使得节点的左子树含有小于该节点的密钥，右子树包含具有更大密钥的节点 - 请参阅维基百科的有关 BST 的文章。然后按顺序遍历按升序检索密钥。为什么你希望降序？




3. 放弃数组可能会更有效，只是递归测试BST的定义条件？
   
   每当我们关注左边链接，我们预计小于当前的键。每当我们遵循正确的链接，我们预计键值会增加当前的值。因此，对于大多数子树，有一些键值的间隔，由一些祖先节点的键定义。只需跟踪这些键并测试键是否落在当前的有效间隔内。确保在最右边的路径上处理no left end defined条件，并在树的最右边的路径上处理no right end。在根节点上没有祖先，所以根目录根本没有测试（任何值都可以）。

编辑

C代码草案：

  //根据最近的左边和右边的祖先测试一个节点
 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）; 
} 
  

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

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

pseudo code

first function

IsBST(node)

size ← TreeSize(node)

create new array TreeArr of Size number of cells

index ← 0

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)

for i from 1 to size-1 do

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

return true

second function

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

else

InOrderArr (node.left, Array, index)

treeArr[index] = node.key

index ← index + 1

InOrderArr (node.right, Array, index)

Return

解决方案

Your code is generally correct. Just three notes.

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.

2. 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?

3. 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).

EDIT

C code draft:

// 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屋！