c++判断是否为满二叉树
时间: 2023-09-11 22:04:22 浏览: 50
判断一棵二叉树是否为满二叉树,需要满足以下条件:
1. 该二叉树的高度为h。
2. 该二叉树的节点数为2^h-1。
以下是C++代码实现:
```c++
//定义二叉树节点
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
//计算二叉树高度
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == NULL)
return 0;
int leftDepth = TreeDepth(pRoot->left);
int rightDepth = TreeDepth(pRoot->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
//计算二叉树节点数
int TreeNodes(TreeNode* pRoot)
{
if(pRoot == NULL)
return 0;
int leftNodes = TreeNodes(pRoot->left);
int rightNodes = TreeNodes(pRoot->right);
return leftNodes + rightNodes + 1;
}
//判断是否为满二叉树
bool isFullTree(TreeNode* pRoot)
{
if(pRoot == NULL)
return true;
int depth = TreeDepth(pRoot);
int nodes = TreeNodes(pRoot);
return nodes == pow(2, depth) - 1;
}
```
其中,TreeDepth函数用于计算二叉树的高度,TreeNodes函数用于计算二叉树的节点数,isFullTree函数用于判断二叉树是否为满二叉树。