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

我有homeowork编写伪代码来检查一个有效的二叉树是否是一个搜索二叉树。伪代码来检查二叉树是否是一个二叉搜索树 - 不确定递归

我创建了一个数组来保存树的有序值。如果顺序值是递减顺序，则意味着它确实是BST。不过，我在InOverArr方法中遇到了递归问题。

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

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

伪代码

第一功能

IsBST（节点）

尺寸←的TreeSize（节点）

创建新的数组TreeArr大小的细胞数
点
指数←0

几点意见：现在我们使用IN_ORDER过程有小的变化，我叫程序的新版本：InOrderArr InOrderArr的伪代码如下IsBST

描述InOrderArr（节点，TreeArr，索引）

对于i从1到尺寸-1做

如果不是（TreeArr [I]> TreeArr [I-1]）返回假

返回真

第二功能

InOrderArr（节点，阵列，索引）如果节点= NULL然后返回

别的

InOrderArr（节点。左，数组，索引）

treeArr [索引] = node.key

索引←索引+ 1

InOrderArr（node.right，阵列，索引）

返回

来源

2014-03-29 CnR

看到我已经加入到我的答案示例代码。 – CiaPan

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

代码的正确性取决于执行情况，特别是对index处理方式。许多编程语言通过值将参数传递给子例程。这意味着子程序接收到该值的副本，并且对该参数所做的修改对原始值没有影响。因此在执行InOrderArr (node.left, Array, index)期间递增index不会影响treeArr[index] = node.key使用的位置。结果只有最右边的路径将被存储在数组中。
为避免这种情况，您必须确保index通过引用传递，以便被调用者完成的增量提前调用者稍后使用的位置。
BST通常被定义为一个节点的左边子树包含的键小于该节点的键，右边的子树包含具有更大键的节点 - 请参阅维基百科关于BST的文章。然后中序遍历按升序检索键。你为什么期望降序？
可能是更有效的删除数组，只是递归地测试BST的定义条件？
每当我们按照left链接，我们期望的键比现有键少。无论何时我们按照right链接，我们都期望按键更大一些。所以对于大多数子树，有一些键值的间隔，由一些祖先节点的键定义。只需跟踪这些密钥并测试密钥是否落入当前有效间隔内。确保在最右边的路径上处理'没有左端定义'的条件，并且在最右边的路径上处理'没有右端'。在根节点上还没有祖先，所以根密钥根本没有测试（任何值都可以）。

编辑

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

来源

2014-03-29 20:34:05 CiaPan

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

回答

相关问题