假设二叉树每个结点的元素均为一个单字符,根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表,然后判断该二叉树是否为二叉排序树。,用C语言写
时间: 2024-05-09 22:14:16 浏览: 103
用C语言编写二叉排序树
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
char data; // 节点的数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
};
// 递归创建二叉树
struct TreeNode* createBinaryTree(char *preorder, int *index, int size) {
if (*index >= size || preorder[*index] == '#') { // 如果已经遍历完或者当前节点为空
(*index)++; // 指针向后移动
return NULL;
}
struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建节点
node->data = preorder[*index]; // 设置节点的数据
(*index)++; // 指针向后移动
node->left = createBinaryTree(preorder, index, size); // 递归创建左子树
node->right = createBinaryTree(preorder, index, size); // 递归创建右子树
return node;
}
// 判断是否为二叉排序树
bool isBST(struct TreeNode* root, char min, char max) {
if (root == NULL) { // 如果节点为空,则返回true
return true;
}
if (root->data <= min || root->data >= max) { // 如果节点的数据不在[min, max]范围内,则返回false
return false;
}
return isBST(root->left, min, root->data) && isBST(root->right, root->data, max); // 递归判断左右子树是否为二叉排序树
}
int main() {
char preorder[] = {'8', '3', '1', '#', '#', '6', '4', '#', '#', '7', '#', '#', '10', '#', '14', '13', '#', '#', '#'}; // 先序遍历序列
int size = sizeof(preorder) / sizeof(char); // 序列的长度
int index = 0; // 指针初始位置为0
struct TreeNode *root = createBinaryTree(preorder, &index, size); // 创建二叉树
if (isBST(root, 0, 127)) { // 判断是否为二叉排序树
printf("This binary tree is a binary search tree.\n");
} else {
printf("This binary tree is not a binary search tree.\n");
}
return 0;
}
```
解释:
1. 首先定义了一个结构体`TreeNode`,表示节点,它包含了节点的数据`data`和左右子树指针`left`和`right`。
2. 然后定义了一个递归函数`createBinaryTree`,用于根据先序遍历的顺序递归创建二叉树。传入参数包括先序遍历序列`preorder`、指针`index`和序列的长度`size`,其中指针`index`用于记录当前遍历到的位置,初始值为0。如果当前节点为空,返回`NULL`;否则,创建节点,设置节点的数据,然后递归创建左右子树。最后返回创建好的节点。
3. 定义了一个函数`isBST`,用于判断二叉树是否为二叉排序树。传入参数包括根节点`root`、节点数据的最小值`min`和最大值`max`。如果节点为空,返回`true`;否则,如果节点的数据不在[min, max]范围内,返回`false`;否则,递归判断左右子树是否为二叉排序树。
4. 在`main`函数中,定义了先序遍历序列`preorder`,以及序列的长度`size`和指针初始位置`index`。然后调用`createBinaryTree`函数创建二叉树,并将根节点赋值给`root`。最后调用`isBST`函数判断是否为二叉排序树,并输出结果。
注意:在本例中,我们假设所有节点的数据都是单字符,因此将节点的数据类型设置为`char`。如果节点的数据类型是其他类型,需要根据具体情况进行修改。
阅读全文