# 11043: 【原1043】完全二叉树

### 题目描述

author: 田力 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1043

## Sample Input1

``````6
0
1
1
0
4
``````

## Sample Output1

``````true
``````

## Sample Input2

``````6
0
1
1
0
3
``````

## Sample Output2

``````false
``````

## FineArtz's solution

``````/* 完全二叉树 */
#include <iostream>
#include <queue>
using namespace std;

class Node{
public:
int lchild = -1, rchild = -1;
};

Node a[1000005];

bool check(int root){
queue<int> q;
q.push(root);
int t = q.front();
q.pop();
while (t != -1){
q.push(a[t].lchild);
q.push(a[t].rchild);
t = q.front();
q.pop();
}
while (!q.empty()){
t = q.front();
q.pop();
if (t != -1) return false;
}
return true;
}

int main(){
int n, t;
cin >> n;
for (int i = 1; i < n; ++i){
cin >> t;
if (a[t].lchild == -1) a[t].lchild = i;
else a[t].rchild = i;
}
if (check(0)) cout << "true" << endl;
else cout << "false" << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

template <class T>
class mQueue {
class node {
public:
T data;
node* next = nullptr;
};
* rear = nullptr;
size_t _size = 0;

public:
//构造函数
mQueue() {
}
//判断是否为空
bool empty() {
}
//增加
void push(const T& val) {
rear->next = new node;
rear = rear->next;
rear->data = val;
++_size;
}
//删除
void pop() {
//安全措施
return;
--_size;
}
//大小
size_t size() {
return _size;
}
//最前
T& front() {
//安全措施
}
//最后
T& back() {
//安全措施
return rear->data;
}
};

//二叉树类
template <class T>
class myBinaryTree {
public:
class node {
public:
T data;
node *lchild = nullptr, *rchild = nullptr,*parent=nullptr;
};
node *root = nullptr;
node **nodeList=nullptr;
int lengthOfNodeList=0;

//创建树
void createTree(int num) {
nodeList = new node*[num+1] {nullptr};
lengthOfNodeList = num;
}

void creadNode(int nodeNum, int child) {
if (nodeList[nodeNum] == nullptr) {
nodeList[nodeNum] = new node;
nodeList[nodeNum]->data = nodeNum;
}

nodeList[child] = new node;
nodeList[child]->data = child;
if (nodeList[nodeNum]->lchild == nullptr) {
nodeList[nodeNum]->lchild = nodeList[child];
}
else {
if (child > nodeList[nodeNum]->lchild->data)
nodeList[nodeNum]->rchild = nodeList[child];
else {
nodeList[nodeNum]->rchild = nodeList[nodeNum]->lchild;
nodeList[nodeNum]->lchild = nodeList[child];
}
}
}

void checkRoot() {
root = nodeList[0];
}

//清空
void clear() {
clear(root);
}

void clear(node *p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rchild);
delete p;
p = nullptr;
}

//构造
myBinaryTree() {}

//析构
~myBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}

//判断是否为完全二叉树
bool isCBT() {
if (empty())
return false;
//层次遍历
mQueue<node*> treeQueue;
bool flag = false;
//先入队
treeQueue.push(root);

//反复
while (!treeQueue.empty()) {
//先出队一个
node* temp = treeQueue.front();
treeQueue.pop();

//右孩子有左孩子没有
if (temp->lchild == nullptr&&temp->rchild != nullptr)
return false;

if (!flag) {
//左孩子有右孩子没有
if (temp->lchild != nullptr&&temp->rchild == nullptr) {
flag = true;
//左孩子入队
treeQueue.push(temp->lchild);
}
//左右孩子都没有
else if (temp->lchild == nullptr&&temp->rchild == nullptr) {
flag = true;
}
//左右都有孩子
else {
treeQueue.push(temp->lchild);
treeQueue.push(temp->rchild);
}
}
else {
//判断是否为叶子
if (temp->lchild != nullptr || temp->rchild != nullptr)
return false;
}
}

return true;
}
};

int main() {
myBinaryTree<int> bTree;
int num;
cin >> num;
if (num == 1) {
cout << "true";
return 0;
}
bTree.createTree(num);

for (int i = 1; i < num; i++) {
int temp;
scanf("%d", &temp);
}
bTree.checkRoot();
cout << (bTree.isCBT()?"true":"false");

return 0;
}
``````

## q4x3's solution

``````/**
* 完全二叉树判断
* 凭直觉写
* 草死了二叉树鲨我
**/
#include <stdio.h>
#include <iostream>

using namespace std;

int N;

struct node{
int self;
int fa;
node *left, *right;
node():fa(-1), left(NULL), right(NULL) {}
};

node no[1000233];
int fa[1000233];

void build() {
for(int i = 0;i <= N;++ i) {
no[i].self = i;
no[i].fa = fa[i];
}
for(int i = 0;i < N;++ i) {
node *fano = &(no[fa[i]]);
node *le = fano->left;
if(le) {
if(le->self > i) {
fano->right = le;
fano->left = &(no[i]);
} else {
fano->right = &(no[i]);
}
} else {
if(i) fano->left = &(no[i]);
}
}
}

bool check(node *rt) {
if(rt == NULL) {
return 0;
}
node* che[1000233];
int head = 0, rear = 0;
che[rear ++] = rt;
if(top->left && top->right) {
che[rear ++] = top->left;
che[rear ++] = top->right;
} else
if(top->left == NULL && top->right) {
return 0;
} else
if((top->left && top->right == NULL) ||
(top->left == NULL && top->right == NULL)) {
if(top->left == NULL && top->right == NULL) {
} else {
return 0;
}
}
return 1;
}
}
return 1;
}

int main() {
scanf("%d", &N);
for(int i = 1;i < N;++ i) {
scanf("%d", &fa[i]);
}
build();
if(check(&(no[0]))) cout << "true" << endl;
else cout << "false" << endl;
return 0;
}
``````

## victrid's solution

``````#include <cstdio>
#include <iostream>
using namespace std;
struct tree {
tree* left;
tree* right;
bool valid;
enum { none,
one,
both } occupied;
tree(int n) : left(nullptr), right(nullptr), valid(true), occupied(none){};
tree() : left(nullptr), right(nullptr), valid(false), occupied(none){};
};
tree nodes[1000001] = {};
//! queue must be large enough to handle a full tree
tree* queuet[4000003] = {nullptr};
tree** queueex;
tree** queueend;
void clearqueue() {
queueex  = queuet;
queueend = queuet + 1;
}
void enqueue(tree* tptr) {
*queueend = tptr;
queueend++;
}
tree* dequeue() {
if (queueex + 1 == queueend)
return nullptr;
else
queueex++;
return *queueex;
}
int main() {
int N;
scanf("%d", &N);
int proc;
nodes[0].valid = true;
for (int i = 1; i < N; i++) {
nodes[i].valid = true;
scanf("%d", &proc);
switch (nodes[proc].occupied) {
case tree::none:
nodes[proc].occupied = tree::one;
nodes[proc].left     = nodes + i;
break;
case tree::one:
nodes[proc].occupied = tree::both;
nodes[proc].right    = nodes + i;
break;
case tree::both:
cout << "false";
return 0;
break;
}
}
clearqueue();
enqueue(nodes);
tree* proce;
int tcount = 0;
proce      = dequeue();
while (proce != nullptr) {
if (!proce->valid)
continue;
tcount++;
proce->valid = false;
enqueue(proce->left);
enqueue(proce->right);
proce = dequeue();
}
if (tcount == N)
cout << "true";
else
cout << "false";
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>

using namespace std;
struct treedata{
int l, r, pre;
} tree[1000001];
int n, i, node, now;
bool flag,complete = true;
queue<int> que;

int main(){
cin>>n;
for (int i = 1; i < n; i++){
cin>>node;
tree[i].pre = node;
if (tree[node].l == 0) tree[node].l = i;
else tree[node].r = i;
}
if (tree[0].l) que.push(tree[0].l);
if (tree[0].r) que.push(tree[0].r);
while (!que.empty()){
now = que.front();
que.pop();
if (!tree[now].l&&!tree[now].r) flag = true;
if (tree[now].l){
que.push(tree[now].l);
if (flag){
complete = false;
break;
}
}
if (tree[now].r) que.push(tree[now].r);
}
if (complete) cout<<"true"; else cout<<"false";
return 0;
}
``````

## Zsi-r's solution

``````#include <iostream>

using namespace std;

struct node
{
int leftchild, rightchild;
node() : leftchild(-1), rightchild(-1){};
bool haveonlyleftchild()
{
return leftchild >= 0 && rightchild == -1;
}
bool haveonlyrightchild()
{
return leftchild == -1 && rightchild >= 0;
}
bool havenochild()
{
return leftchild == -1 && rightchild == -1;
}
bool havebothchild()
{
return leftchild >= 0 && rightchild >= 0;
}
};

class que
{
struct n
{
node data;
n *next;
n(const node &x,n*n = NULL)
{
data = x;
next = n;
}
n():next(NULL){}
~n(){}
};

n *front, *rear;
public:
que() { front = rear = NULL; }
bool isempty()
{
return front == NULL;
}
~que() {
n *temp;
while(front!=NULL)
{
temp = front;
front = front->next;
delete temp;
}
}
void enqueue(const node &x)
{
if (rear==NULL)
front = rear = new n(x);
else
{
rear->next = new n(x);
rear = rear->next;
}
}
node dequeue()
{
n *temp = front;
node value = front->data;
front = front->next;
if (front ==NULL)
rear = NULL;
delete temp;
return value;
}

};

class tree
{
friend istream & operator>>(istream &is,tree &obj)
{
int temp;
for (int i = 1; i < obj.len;i++)
{
cin >> temp;
if (obj.list[temp].havenochild())
obj.list[temp].leftchild = i;
else if (obj.list[temp].haveonlyleftchild())
obj.list[temp].rightchild = i;
}
return is;
}
private:
node *list;
int len;
bool iscbt(int n)
{
que q;
if (list[n].havenochild())
return true;
bool flag = false;
q.enqueue(list[n]);
while(!q.isempty())
{
node temp = q.dequeue();
if (temp.haveonlyrightchild())
return false;
if (!flag){
if (temp.havebothchild())
{
q.enqueue(list[temp.leftchild]);
q.enqueue(list[temp.rightchild]);
continue;
}
else if (temp.haveonlyleftchild())
{
q.enqueue(list[temp.leftchild]);
flag = true;
continue;
}
else if (temp.havenochild())
{
flag = true;
continue;
}
}
else{
if (!temp.havenochild())
return false;
}
}
return true;
}
public:
tree(int n){
list = new node[n];
len = n;
}
bool iscbt()
{
return iscbt(0);
}
};

int main()
{
int n;
cin >> n;
tree t(n);
cin >> t;
bool flag = t.iscbt();
if (flag)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
``````