【题目要求】
设计算法判断一棵树是否为完全二叉树。
【提示】
根据完全二叉树的定义可知:
1)如果一个结点有右孩子而没有左孩子,那么这棵树一定不是完全二叉树。
2)如果一个结点有左孩子,而没有右孩子,那么按照层序遍历的结果,这个结点之后的所有结点都是叶子结点,这棵树才是完全二叉树。
3)如果一个结点是叶子结点,那么按照层序遍历的结果,这个结点之后的所有结点都必须是叶子结点这棵树才是完全二叉树。
【测试样例】
【输入】
AB#D##C##
【输出】
层序遍历:ABCD
判断是否是完全二叉树:不是
【题解代码
】
//借助队列用层序遍历实现
#include<iostream>
#include<queue>
using namespace std;
const int QUEUESIZE = 100;
struct BiNode {
char data;
BiNode* lchild, * rchild;
};
class BiTree
{
private:
BiNode* root;
public:
BiTree() { root = creat(root); }
~BiTree() {
release(root);
}
BiNode* getRoot() { return root; }
BiNode* creat(BiNode* bt); //构造函数调用
void release(BiNode* bt); //析构函数调用,释放树的存储空间
void leverOrder(BiNode* bt);//层序遍历函数调用
bool isCompleteBiTree(BiNode* bt);//判断是否为完全二叉树
};
BiNode* BiTree::creat(BiNode* bt)
{
char ch;
cin >> ch;
if (ch == '#')
bt = NULL;
else
{
bt = new BiNode;
bt->data = ch;
bt->lchild = creat(bt->lchild);
bt->rchild = creat(bt->rchild);
}
return bt;
}
void BiTree::release(BiNode* bt)
{
if (bt != NULL)
{
release(bt->lchild);
release(bt->rchild);
// cout<<"delete "<<bt->data<<endl;
delete bt;
}
}
void BiTree::leverOrder(BiNode* bt)
{
BiNode* q;
queue<BiNode*> Q;
Q.push(root);
if (root == NULL)
return;
while (!Q.empty())
{
q = Q.front();
cout << q->data;
Q.pop();
if (q->lchild != NULL)
Q.push(q->lchild);
if (q->rchild != NULL)
Q.push(q->rchild);
}
}
bool BiTree::isCompleteBiTree(BiNode* bt)
{
if (bt == NULL)
return true;
queue<BiNode*> Q;
Q.push(bt);
bool flag = false;
while (!Q.empty())
{
BiNode* node = Q.front();
Q.pop();
if (node->lchild) //如果左孩子存在
{
if (flag) //但是前面有缺失的结点
return false; //不是完全二叉树
else //前面是结点是满的
Q.push(node->lchild); //把左孩子入队
}
else
{
flag = true; //左孩子结点缺失,为了下一次判断需要将flag定为真
}
if (node->rchild) //右孩子结点存在
{
if (flag) //前面有缺失的结点
return false;//不是完全二叉树
else
Q.push(node->rchild);//否则,右孩子入队
}
else
flag = true;//右孩子结点缺失,为了下一次判断需要将flag定为真
}
return true;
}
int main() {
BiTree tree;
cout << "层序遍历:";
tree.leverOrder(tree.getRoot());
cout << endl;
cout << "判断是否是完全二叉树:";
if (tree.isCompleteBiTree(tree.getRoot()))
cout << "是" << endl;
else
cout << "不是" << endl;
return 0;
}
标签:lchild,BiNode,结点,--,c++,bt,二叉树,rchild
From: https://blog.csdn.net/2301_79790771/article/details/137085029