c语言中判断给定二叉树是否二叉搜索树
时间: 2023-12-16 08:06:17 浏览: 50
在C语言中,判断给定的二叉树是否为二叉搜索树可以通过中序遍历来实现。
二叉搜索树的中序遍历序列是单调递增的,因此可以在中序遍历的过程中判断当前节点值是否大于前一个节点值。如果大于,则说明不是二叉搜索树。
下面是一个简单的C语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义二叉树节点
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 中序遍历二叉树
bool inorder(TreeNode* root, int* prev) {
if (root == NULL) {
return true;
}
if (!inorder(root->left, prev)) {
return false;
}
if (root->val <= *prev) {
return false;
}
*prev = root->val;
return inorder(root->right, prev);
}
// 判断是否为二叉搜索树
bool isValidBST(TreeNode* root) {
int prev = INT_MIN;
return inorder(root, &prev);
}
```
在这个代码中,我们定义了一个`TreeNode`结构体表示二叉树节点,它包含一个整数值`val`,以及左右子节点的指针。然后我们定义了一个`inorder`函数来进行中序遍历,并在遍历过程中判断是否为二叉搜索树。最后,我们定义了一个`isValidBST`函数来调用`inorder`函数进行判断。