编写一个C 语言程序:请实现一个函数,打印给定二叉树的中序遍历序列并判定他是否是一棵二叉搜索树(Binary Search Tree)。
时间: 2023-06-15 14:06:08 浏览: 103
以下是一个示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
// 二叉树结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 中序遍历函数
void inorderTraversal(struct TreeNode* root, int* arr, int* index) {
if (root == NULL) {
return;
}
inorderTraversal(root->left, arr, index);
arr[(*index)++] = root->val;
inorderTraversal(root->right, arr, index);
}
// 判断是否为二叉搜索树
bool isValidBST(struct TreeNode* root) {
int arr[10000];
int index = 0;
inorderTraversal(root, arr, &index);
for (int i = 0; i < index - 1; i++) {
if (arr[i] >= arr[i+1]) {
return false;
}
}
return true;
}
int main() {
// 构建二叉树
struct TreeNode node1 = {1, NULL, NULL};
struct TreeNode node3 = {3, NULL, NULL};
struct TreeNode node2 = {2, &node1, &node3};
// 判断是否为二叉搜索树
if (isValidBST(&node2)) {
printf("是一棵二叉搜索树\n");
} else {
printf("不是一棵二叉搜索树\n");
}
return 0;
}
```
这个程序中,`inorderTraversal` 函数实现了中序遍历,并将遍历的结果存储在一个数组中。`isValidBST` 函数则使用了中序遍历的结果来判断是否为二叉搜索树。遍历过程中,只要发现当前节点的值不大于前一个节点的值,就说明不是一棵二叉搜索树。如果遍历结束了都没有发现这种情况,就说明是一棵二叉搜索树。
阅读全文