用C语言写一个判别给定二叉树是否为二叉树的算法
时间: 2024-03-01 15:22:54 浏览: 76
C语言非递归后序遍历二叉树
5星 · 资源好评率100%
以下是C语言实现的判别给定二叉树为二叉树的算:
```c
#includestdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 判断二叉树是否为二叉树
bool isBinaryTree(TreeNode *root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBinaryTree(root->left, min, root->data - 1) && isBinaryTree(root->right, root->data + 1, max);
}
int main() {
// 构造一个二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = 4;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->data = 2;
root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->left->data = 1;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
root->left->right->data = 3;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->data = 6;
root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
root->right->left->data = 5;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->data = 7;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 判断是否为二叉树
bool isBinary = isBinaryTree(root, INT_MIN, INT_MAX);
if (isBinary) {
printf("The given tree is a binary tree\n");
} else {
printf("The given tree is not a binary tree\n");
}
return 0;
}
```
该算法使用递归的方式进行判断,如果当前节点为空则是二叉树,否则判断是否满足二叉树的条件,即左子树的所有节点值都小于当前节点的值,右子树的所有节点值都大于当前节点的值,递归进行判断。在判断过程中,使用min和max表示当前节点需要满足的最小值和最大值,初始值为INT_MIN和INT_MAX。
阅读全文