编写算法,判断二叉树是否为二叉排列数,设此二叉树以二叉链表为存储结构,而且树中结点的关键字都不同,C语言编程
时间: 2024-03-25 11:37:49 浏览: 62
线索链表的遍历算法:-数据结构:树和二叉树 课件
以下是判断二叉树是否为二叉排列树的 C 语言代码:
```c
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
int isBST(struct node* node, struct node* left, struct node* right)
{
if (node == NULL)
return 1;
if (left != NULL && node->key <= left->key)
return 0;
if (right != NULL && node->key >= right->key)
return 0;
return isBST(node->left, left, node) &&
isBST(node->right, node, right);
}
int main()
{
struct node *root = (struct node*)malloc(sizeof(struct node));
root->key = 4;
root->left = (struct node*)malloc(sizeof(struct node));
root->left->key = 2;
root->left->left = (struct node*)malloc(sizeof(struct node));
root->left->left->key = 1;
root->left->right = (struct node*)malloc(sizeof(struct node));
root->left->right->key = 3;
root->right = (struct node*)malloc(sizeof(struct node));
root->right->key = 6;
root->right->left = (struct node*)malloc(sizeof(struct node));
root->right->left->key = 5;
root->right->right = (struct node*)malloc(sizeof(struct node));
root->right->right->key = 7;
if(isBST(root, NULL, NULL))
printf("This is a binary search tree.");
else
printf("This is not a binary search tree.");
return 0;
}
```
在此代码中,我们首先定义了一个结构体 `node`,其中包含了二叉树的关键字和左右孩子结点的指针。然后,我们定义了一个 `isBST` 函数,用于判断一棵二叉树是否为二叉排列树。该函数有三个参数,分别是当前结点、当前结点的左孩子和右孩子。函数中使用了递归的方法来进行判断:首先,如果当前结点为 `NULL`,则返回 1;否则,如果当前结点的关键字小于等于左孩子的关键字,或者大于等于右孩子的关键字,则返回 0;最后,递归判断左子树和右子树是否满足二叉排列树的性质。
在 `main` 函数中,我们手动构造了一棵二叉树,并调用 `isBST` 函数进行判断,最终输出判断结果。
阅读全文