使用c语言,写 一个判别给定二叉树是否为二叉排序树的算法。
时间: 2024-01-14 19:13:09 浏览: 26
以下是使用C语言实现判断二叉树是否为二叉排序树的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node {
int data;
struct node *left;
struct node *right;
};
int isBSTUtil(struct node* node, int min, int max);
int isBST(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(struct node* node, int min, int max) {
if (node == NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data - 1) &&
isBSTUtil(node->right, node->data + 1, max);
}
struct node* newNode(int data) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main() {
struct node *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);
if (isBST(root))
printf("Given binary tree is a Binary Search Tree");
else
printf("Given binary tree is NOT a Binary Search Tree");
return 0;
}
```
这个算法的时间复杂度为O(n),其中n是二叉树的节点数。