编写一个C 语言程序:请实现一个函数,打印给定二叉树的中序遍历序列并判定他是否是一棵二叉搜索树(Binary Search Tree)。
时间: 2023-06-15 16:06:05 浏览: 81
以下是实现该功能的 C 代码:
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 定义二叉树结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 中序遍历二叉树并判断是否为二叉搜索树
bool inorderTraversal(struct TreeNode *root, int *prev) {
if (root == NULL) {
return true;
}
if (!inorderTraversal(root->left, prev)) {
return false;
}
if (root->val <= *prev) {
return false;
}
*prev = root->val;
return inorderTraversal(root->right, prev);
}
bool isValidBST(struct TreeNode* root){
int prev = INT_MIN;
return inorderTraversal(root, &prev);
}
// 创建二叉树
struct TreeNode* createTree(int *arr, int start, int end) {
if (start > end) {
return NULL;
}
int mid = (start + end) / 2;
struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = arr[mid];
root->left = createTree(arr, start, mid-1);
root->right = createTree(arr, mid+1, end);
return root;
}
// 打印中序遍历序列
void inorderPrint(struct TreeNode *root) {
if (root == NULL) {
return;
}
inorderPrint(root->left);
printf("%d ", root->val);
inorderPrint(root->right);
}
// 测试代码
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int len = sizeof(arr) / sizeof(arr[0]);
struct TreeNode *root = createTree(arr, 0, len-1);
inorderPrint(root);
printf("\nThis tree is %s a binary search tree.\n", isValidBST(root) ? "" : "not");
return 0;
}
```
该程序首先利用给定的数组创建一棵平衡二叉搜索树,然后打印出它的中序遍历序列。最后,利用 `inorderTraversal` 函数判断该二叉树是否为二叉搜索树。
需要注意的是,该程序中的 `inorderTraversal` 函数利用了指向前驱节点的指针 `prev`,用于判断当前节点和它的前驱节点的大小关系。在最开始调用 `isValidBST` 函数时,将 `prev` 初始化为整型最小值 `INT_MIN`。