判断一棵树是否是完全二叉树
程序员文章站
2022-05-16 10:59:02
...
首先要知道完全二叉树的定义: 前n-1层都是满的,第n层如有空缺,则是右边有空缺,即第n层的右边的某个节点开始有空缺,它的左边是满的,右边是空的。
以二叉搜索树举例。
#include <bits/stdc++.h>
using namespace std;
typedef struct BNode* BTree;
struct BNode
{
int data;
BTree left;
BTree right;
};
void Insert(BTree &t,int data){
if(!t){
BTree p=(BTree)malloc(sizeof(BTree));
p->data=data;
p->left=NULL;
p->right=NULL;
t=p;
}
else if(data<t->data)Insert(t->left,data);
else if(data>=t->data)Insert(t->right,data);
}
bool IsComplateTree(BTree root){
queue<BTree> q;
if (root){
q.push(root);
}
bool f = true;
while (!q.empty()){
BTree front = q.front();
q.pop();
if (front->left){
if (f == false){
return false;
}
q.push(front->left);
}
else f = false;
if (front->right){
if (f == false){
return false;
}
q.push(front->right);
}
else f = false;
}
return true;
}
int main()
{
int n;
int a[1001];
cin>>n;
BTree t=NULL;
for(int i=0;i<n;i++){
cin>>a[i];
Insert(t,a[i]);
}
if(IsComplateTree(t))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
上一篇: 8个流行的Python可视化工具包。
下一篇: Kali之Beef利用Xss进行钓鱼