假设二叉树每个结点的元素均为一个单字符,根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表,然后判断该二叉树是否为二叉排序树。(用C语言)
时间: 2023-06-20 20:04:11 浏览: 146
建立一个二叉树,判断是不是二叉排序树!
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createTree(char* str, int* idx) {
if (str[*idx] == '#') {
(*idx)++;
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = str[(*idx)++];
node->left = createTree(str, idx);
node->right = createTree(str, idx);
return node;
}
int isBST(struct TreeNode* root, char min, char max) {
if (root == NULL) {
return 1;
}
if (root->val < min || root->val > max) {
return 0;
}
return isBST(root->left, min, root->val - 1) && isBST(root->right, root->val + 1, max);
}
int main() {
char* str = "8B4##1##3##6A##";
int idx = 0;
struct TreeNode* root = createTree(str, &idx);
if (isBST(root, ' ', '~')) {
printf("This is a Binary Search Tree.\n");
} else {
printf("This is not a Binary Search Tree.\n");
}
return 0;
}
```
在这里,我们首先通过递归创建二叉树。然后,我们使用isBST()函数来判断它是否为二叉搜索树。isBST()函数采用最小值和最大值作为参数来限制每个节点的值必须在该范围内。如果该树是BST,则返回1,否则返回0。
在这个示例中,我们创建了一个二叉树,并使用先序遍历字符串表示。输出结果表明,该树是一个二叉搜索树。
阅读全文