编写算法判别给定二叉树是否为2x排序数是此二叉数以二叉链表为存储结构且树中节点的关键词均不同C语言
时间: 2024-03-23 17:42:59 浏览: 126
写一算法,判断一棵二叉树是否是一棵二叉排序树。
以下是使用C语言实现判断给定二叉树是否为2x排序树的算法:
```c
#include <stdio.h>
#include <stdbool.h>
typedef struct node {
int val;
struct node* left;
struct node* right;
} Node;
bool is_bst(Node* root) {
if (root == NULL) {
return true;
}
if (root->left != NULL && root->left->val >= root->val) {
return false;
}
if (root->right != NULL && root->right->val <= root->val) {
return false;
}
return is_bst(root->left) && is_bst(root->right);
}
bool is_2x_bst(Node* root) {
if (root == NULL) {
return true;
}
if (root->left != NULL && !is_bst(root->left)) {
return false;
}
if (root->right != NULL && !is_bst(root->right)) {
return false;
}
return is_2x_bst(root->left) && is_2x_bst(root->right);
}
int main() {
Node* root = (Node*)malloc(sizeof(Node));
root->val = 10;
root->left = (Node*)malloc(sizeof(Node));
root->left->val = 5;
root->left->left = (Node*)malloc(sizeof(Node));
root->left->left->val = 2;
root->left->right = (Node*)malloc(sizeof(Node));
root->left->right->val = 7;
root->right = (Node*)malloc(sizeof(Node));
root->right->val = 15;
root->right->left = (Node*)malloc(sizeof(Node));
root->right->left->val = 12;
root->right->right = (Node*)malloc(sizeof(Node));
root->right->right->val = 20;
if (is_2x_bst(root)) {
printf("The given binary tree is a 2x BST.\n");
} else {
printf("The given binary tree is not a 2x BST.\n");
}
return 0;
}
```
上述代码通过递归实现了判断二叉树是否为2x排序树的算法,其中is_bst函数用于判断一棵二叉树是否为排序树,is_2x_bst函数用于判断一棵二叉树是否为2x排序树。在主函数中,我们创建了一棵二叉树并进行了测试。
阅读全文