数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序检查给定的二叉树是否为满二叉树
给定一棵二叉树，任务是检查它是否为满二叉树。如果每个节点都有零个或两个子节点，则称二叉树为满二叉树。
例如
输入-1
输出
1
解释：除了叶子节点之外，每个节点都有两个子节点，因此它是一棵满二叉树。
输入-2：
输出
0
解释：节点 2 只有一个子节点，因此它不是一棵满二叉树。
解决此问题的方法
要检查给定的二叉树是否为满二叉树，我们可以递归地检查左子树和右子树。
- 输入具有节点及其子节点的给定二叉树。
- 布尔函数 isFullBinaryTree(Node*root) 以根节点作为输入，如果它是满二叉树则返回 True，否则返回 false。
- 在基本条件下，如果根节点为空或为空，则返回 True。
- 如果左子树和右子树为空或为空，则返回 True。
- 现在让我们递归地检查每个左子树和右子树并返回输出。
示例
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isFullBinaryTree(struct treenode * root) {
if (root == NULL) {
return true;
}
if (root -> left == NULL and root -> right == NULL) {
return true;
} else if (root -> left and root -> right) {
return (isFullBinaryTree(root -> left) and isFullBinaryTree(root -> right));
}
return false;
}
int main() {
struct treenode * root = NULL;
root = createNode(1);
root -> left = createNode(2);
root -> right = createNode(3);
root -> left -> right = createNode(4);
root -> left -> left = createNode(5);
root -> right -> left = createNode(6);
if (isFullBinaryTree(root)) {
cout << "1" << endl;
} else {
cout << "0" << endl;
}
return 0;
}运行以上代码将生成以下输出：
输出
0
解释：由于给定二叉树中的所有叶子节点都没有子节点，因此它不是满二叉树。所以，我们得到输出为 0。
更新于： 2021年2月23日
1K+ 浏览量
广告