Skip to content

11043: 【原1043】完全二叉树

题目

题目描述

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

Description

给出一棵二叉树，判断其是否为完全二叉树。

Input Format

第一行，N<1000000，表示二叉树节点数。

默认序号为0的节点为树根。接下来共N-1行，依次表示序号为1，...，N-1的节点的父亲节点序号。

如果一个节点有两个孩子节点，左孩子节点序号总是小于右孩子节点序号。

Output Format

仅一行，如果是完全二叉树，则输出true，否则输出false。

Hint

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;
    };
    node* head = nullptr,
        * rear = nullptr;
    size_t _size = 0;

public:
    //构造函数
    mQueue() {
        head = new node;
        rear = head;
    }
    //判断是否为空
    bool empty() {
        return head->next == nullptr;
    }
    //增加
    void push(const T& val) {
        rear->next = new node;
        rear = rear->next;
        rear->data = val;
        ++_size;
    }
    //删除
    void pop() {
        //安全措施
        if (head->next == nullptr)
            return;
        auto temp = head->next;
        delete head;
        head = temp;
        --_size;
    }
    //大小
    size_t size() {
        return _size;
    }
    //最前
    T& front() {
        //安全措施
        return head->next->data;
    }
    //最后
    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.creadNode(temp, i);
    }
    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;
    while(head != rear) {
        node *top = che[head];
        if(top->left && top->right) {
            ++ head;
            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)) {
            ++ head;
            while(head != rear) {
                top = che[head];
                if(top->left == NULL && top->right == NULL) {
                    ++ head;
                } 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;
}