7-8 中序遍历树并判断是否为二叉搜索树 (20 分)
时间: 2023-04-23 07:07:28 浏览: 128
中序遍历树是指按照左子树-根节点-右子树的顺序遍历整棵树。
判断一棵树是否为二叉搜索树,需要满足以下条件:
1. 左子树的所有节点的值都小于根节点的值;
2. 右子树的所有节点的值都大于根节点的值;
3. 左子树和右子树都必须是二叉搜索树。
因此,我们可以通过中序遍历树,并判断遍历的节点值是否递增来判断一棵树是否为二叉搜索树。具体实现可以使用递归或者栈来完成。
相关问题
用C++语言写一个通过中序遍历判断是否为二叉搜索树的代码
好的,以下是用 C 语言编写的通过中序遍历判断是否为二叉搜索树的代码:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 判断二叉树是否为二叉搜索树
bool isValidBST(TreeNode* root) {
static TreeNode* prev = NULL;
if (root == NULL) {
return true;
}
if (!isValidBST(root->left)) {
return false;
}
if (prev != NULL && prev->val >= root->val) {
return false;
}
prev = root;
return isValidBST(root->right);
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
// 创建一棵二叉搜索树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 4;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 1;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 3;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 6;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 5;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 7;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 输出中序遍历序列
printf("中序遍历序列为:");
inorderTraversal(root);
printf("\n");
// 判断是否为二叉搜索树并输出结果
bool result = isValidBST(root);
printf("是否为二叉搜索树:%s\n", result ? "是" : "否");
return 0;
}
```
该代码中,isValidBST 函数通过递归方式中序遍历二叉树,并记录上一个访问的节点 prev,判断当前节点和 prev 的值大小关系是否符合二叉搜索树的定义。如果符合,更新 prev 的值为当前节点,继续访问右子树。如果不符合,返回 false,代表该二叉树不是二叉搜索树。而 inorderTraversal 函数则是为了输出中序遍历序列方便代码测试。
写一个通过中序遍历判断是否为二叉搜索树的代码
以下为判断二叉树是否为二叉搜索树的 Python 代码:
```python
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def is_bst(root, min_val=float('-inf'), max_val=float('inf')):
if root is None:
return True
if root.val <= min_val or root.val >= max_val:
return False
return is_bst(root.left, min_val, root.val) and is_bst(root.right, root.val, max_val)
# 测试代码
if __name__ == '__main__':
root = TreeNode(5)
root.left = TreeNode(2)
root.right = TreeNode(9)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
print(is_bst(root)) # True
```
以上代码中,is_bst() 函数使用递归方式判断二叉树是否为二叉搜索树。对于每个节点,它的左子树的所有节点要小于当前节点的值,它的右子树的所有节点要大于当前节点的值。如果不满足这个条件,则返回 False。