c语言判断二叉排序树
时间: 2023-08-03 11:03:31 浏览: 89
判断一棵二叉树是否为二叉排序树可以采用中序遍历的方法,如果遍历结果是递增的则说明是二叉排序树,否则不是。
以下是C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// 插入节点
Node* insertNode(Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
// 中序遍历二叉树
void inorderTraversal(Node* root, int* prev, int* flag) {
if (root == NULL || *flag == 0) {
return;
}
inorderTraversal(root->left, prev, flag);
if (root->data < *prev) {
*flag = 0;
return;
}
*prev = root->data;
inorderTraversal(root->right, prev, flag);
}
// 判断二叉树是否为二叉排序树
int isBST(Node* root) {
int prev = -2147483648; // int类型最小值
int flag = 1; // 标记是否为二叉排序树
inorderTraversal(root, &prev, &flag);
return flag;
}
int main() {
Node* root = NULL;
root = insertNode(root, 4);
root = insertNode(root, 2);
root = insertNode(root, 6);
root = insertNode(root, 1);
root = insertNode(root, 3);
root = insertNode(root, 5);
root = insertNode(root, 7);
if (isBST(root)) {
printf("This is a binary search tree.\n");
} else {
printf("This is not a binary search tree.\n");
}
return 0;
}
```
以上代码中,`createNode()` 函数用于创建新节点,`insertNode()` 函数用于插入节点,`inorderTraversal()` 函数用于中序遍历二叉树并判断是否为二叉排序树,`isBST()` 函数用于调用 `inorderTraversal()` 函数并返回结果。在 `main()` 函数中,我们先构建一棵二叉树,然后调用 `isBST()` 函数来判断是否为二叉排序树。
阅读全文