用C语言编写程序,创建二叉树,二叉树按链表方式存放,且树中结点关键字均不同,写一个判别该二叉树是否为二叉排序树的算法
时间: 2023-11-18 10:02:10 浏览: 118
写一算法,判断一棵二叉树是否是一棵二叉排序树。
以下是用C语言编写的判断二叉树是否为二叉排序树(BST)的算法,其基本思路是采用中序遍历二叉树,如果遍历的结果是按照升序排列的,则该二叉树为BST。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
//定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
//创建一颗二叉树
TreeNode *createTree() {
int val;
scanf("%d", &val);
if (val == -1) { //如果输入-1,则表示该节点为空
return NULL;
} else {
TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = createTree();
newNode->right = createTree();
return newNode;
}
}
int prev = -65535; //记录前一个遍历的节点的值
//中序遍历二叉树,判断是否为BST
int isBST(TreeNode *root) {
if (root == NULL) {
return true;
}
//中序遍历左子树
if (!isBST(root->left)) {
return false;
}
//比较当前节点的值和前一个节点的值
if (root->val <= prev) {
return false;
}
prev = root->val;
//中序遍历右子树
if (!isBST(root->right)) {
return false;
}
return true;
}
int main() {
TreeNode *root = createTree();
if (isBST(root)) {
printf("这是一颗二叉排序树\n");
} else {
printf("这不是一颗二叉排序树\n");
}
return 0;
}
```
在主函数中,我们调用`createTree`函数创建一颗二叉树,然后调用`isBST`函数判断该二叉树是否为BST。`isBST`函数的实现采用了递归的方式进行中序遍历,具体实现如下:
1. 如果当前节点为空,则返回true。
2. 对当前节点的左子树进行中序遍历,如果返回false,则说明左子树不是BST,直接返回false。
3. 比较当前节点的值和前一个节点的值,如果当前节点的值小于等于前一个节点的值,则说明不满足BST的条件,直接返回false。
4. 记录当前节点的值为前一个遍历的节点的值。
5. 对当前节点的右子树进行中序遍历,如果返回false,则说明右子树不是BST,直接返回false。
6. 如果以上条件都不满足,则说明该二叉树是BST,返回true。
最后,我们输出判断的结果即可。
阅读全文