打印 "The BST is in order" 的二叉搜索树 (BST) 顺序访问

Question

我目前正在做一个二叉搜索树项目，我想实现一个“inorder”访问函数：

void inorder(struct node *root)
{
    if(root!=NULL) // checking if the root is not null
    {
        inorder(root->left_child); // visiting left child
        printf(" %d ", root->data); // printing data at root
        inorder(root->right_child);// visiting right child
    }
}

不过我确实有一个小问题，我的 BST 在 100000 到 1000000 个密钥之间变化，正如您可以想象的那样，将它们全部打印出来并不是很“方便”。有没有办法以只打印“The BST is in order”的方式修改这个 inorder 函数？我一直在尝试实现它，但我真的找不到解决方案。

在此先感谢您的帮助！祝你编程愉快！

Answer 1

看起来你想验证一棵树是否真的是有效 BST，即它的中序遍历会访问它的非递减顺序的值。

为此你需要一个不同的函数。这是如何完成的：

int isValidBstHelper(struct node *root, int low, int high) {
    return root == NULL || 
        (root->data >= low && root->data <= high &&
         isValidBstHelper(root->left_child, low, root->data) &&
         isValidBstHelper(root->right_child, root->data, high)); 
}

int isValidBst(struct node *root) {
    return isValidBstHelper(root, INT_MIN, INT_MAX);
}

isValidBst 将 return 当树是有效 BST 时为 1，否则为 0。

要打印结果，只需这样调用：

if (isValidBst(root)) {
    printf("The tree is a valid BST");
} else {
    printf("The tree is NOT a valid BST");
}

打印 "The BST is in order" 的二叉搜索树 (BST) 顺序访问

Binary search tree (BST) inorder visit that prints "The BST is in order"

inorder

binary-search-tree