Skip to content

11212: 【原1212】levelOrder

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1212

Description

给出一棵二叉树的结构以及各个结点的权值,要求按层次遍历二叉树并输出各个结点的权值。必须使用二叉树类实现。

Input Format

输入文件一共包含N+1行。

第一行含有一个正整数N,代表树中结点总数。

第二行到第N+1行,每行包含三个整数。其中第i行的三个整数Pi,Qi,Vi,代表结点i的左孩子为Pi,右孩子为Qi,结点i自身的权值为Vi。若Pi=0,则表明结点i没有左孩子。同样的,若Qi=0,则表明结点i没有右孩子。(第i行指的是这N行中的第i行)

Output Format

输出包含N个数,表示按题目要求顺序输出的各个结点的权值,用一个空格隔开。

Sample Input1

4
0 0 1
3 1 2
0 0 3
0 2 4

Sample Output1

4 2 3 1

Sample Input2

4
0 2 1
0 3 2
0 4 3
0 0 4

Sample Output2

1 2 3 4

Limit

对于所有的数据,均满足1<=N<=100000

对于所有的数据,均满足0<=Pi,Qi<=N

对于所有的数据,均满足-2147483648<=Vi<=2147483647

对于所有的数据,均保证给出的是一棵二叉树

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;
    long long sizeOfTree= 0;

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

    void creadNode(int nodeNum, int lchild, int rchild,int data) {
        if (nodeList[nodeNum] == nullptr)
            nodeList[nodeNum] = new node;

        nodeList[nodeNum]->data = data;

        if (lchild != 0) {
            if (nodeList[lchild] == nullptr)
                nodeList[lchild] = new node;
            nodeList[lchild]->parent = nodeList[nodeNum];
            nodeList[nodeNum]->lchild = nodeList[lchild];
        }

        if (rchild != 0) {
            if (nodeList[rchild] == nullptr)
                nodeList[rchild] = new node;
            nodeList[rchild]->parent = nodeList[nodeNum];
            nodeList[nodeNum]->rchild = nodeList[rchild];
        }
    }

    void checkRoot() {
        for (int i = 1; i <= sizeOfTree; i++) {
            if (nodeList[i]->parent == nullptr) {
                root = nodeList[i];
                break;
            }
        }
    }

    //清空
    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;
    }

    //返回大小
    long long size() {
        return sizeOfTree;
    }

    //层次遍历
    T* levelTraversal(){
        if (sizeOfTree == 0)
            return NULL;

        T *result = new T[sizeOfTree];
        mQueue<node*> treeQueue;
        long long pos = 0;
        //根结点入队
        treeQueue.push(root);

        //层次遍历
        while (!treeQueue.empty()) {
            //出队
            node* temp= treeQueue.front();
            treeQueue.pop();

            //入队
            if (temp->lchild != nullptr)
                treeQueue.push(temp->lchild);
            if (temp->rchild != nullptr)
                treeQueue.push(temp->rchild);

            //写入
            result[pos++] = temp->data;
        }

        //返回
        return result;
    }
};

int main() {
    int num;
    myBinaryTree<int> bTree;
    cin >> num;
    bTree.createTree(num);

    for (int i = 1; i <= num; i++) {
        int lchild, rchild, nodeData;
        scanf("%d %d %d", &lchild, &rchild, &nodeData);
        bTree.creadNode(i, lchild, rchild, nodeData);
    }

    bTree.checkRoot();
    auto ans = bTree.levelTraversal();

    cout << ans[0];
    for (int i = 1; i < bTree.sizeOfTree; i++)
        printf(" %d", ans[i]);

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 100000;
int leftNum[maxN + 100] = {0}, rightNum[maxN + 100] = {0},
                   numNum[maxN + 100] = {0};

template <class elemType>
class queue {
   public:
    virtual bool isEmpty() const = 0;
    virtual void enQueue(const elemType &) = 0;
    virtual elemType deQueue() = 0;
    virtual elemType getHead() const = 0;
    virtual ~queue() {}
};

template <class elemType>
class seqQueue : public queue<elemType> {
   private:
    elemType *data;
    int maxSize;
    int front, rear;
    void doubleSpace();

   public:
    seqQueue(int size = maxN + 100);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &);
    elemType deQueue();
    elemType getHead() const;
    int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = data;
    data = new elemType[maxSize * 2];

    for (int i = 1; i <= maxSize; i++) {
        data[i] = tmp[(front + i) % maxSize];
    }

    front = 0;
    rear = maxSize;
    maxSize *= 2;
    delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
    data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
    delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
    return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    if ((rear + 1) % maxSize == front) {
        doubleSpace();
    }
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;
    return data[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
    return ((rear + maxSize - front) % maxSize);
}

template <class T>
class bTree {
   private:
    struct Node {
        T data;
        Node *left;
        Node *right;
        Node *parent;

        Node(T d = 0, Node *p = 0, Node *l = 0, Node *r = 0)
            : data(d), parent(p), left(l), right(r) {}
    };
    Node *root;
    Node *nodes[maxN + 100];
    void clear(Node *);

   public:
    bTree(int n = 10);
    ~bTree();
    void addNode(int, int, T, bool);
    void findRoot();
    void levelOrder() const;
};

template <class T>
bTree<T>::bTree(int n) : root(NULL) {
    for (int i = 1; i <= n + 5; i++) {
        nodes[i] = new Node;
    }
}

template <class T>
bTree<T>::~bTree() {
    clear(root);
}

template <class T>
void bTree<T>::clear(Node *p) {
    if (p == NULL) {
        return;
    }

    clear(p->left);
    clear(p->right);
    delete p;
}

template <class T>
void bTree<T>::addNode(int n, int i, T x, bool isRight) {
    if (i != 0 && !isRight) {
        nodes[i]->parent = nodes[n];
        nodes[n]->left = nodes[i];
    } else if (i != 0 && isRight) {
        nodes[i]->parent = nodes[n];
        nodes[n]->right = nodes[i];
    }
    nodes[n]->data = x;
}

template <class T>
void bTree<T>::findRoot() {
    root = nodes[1];
    while (root->parent != NULL) {
        root = root->parent;
    }
}

template <class T>
void bTree<T>::levelOrder() const {
    seqQueue<Node *> que;
    Node *tmp;

    que.enQueue(root);

    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << tmp->data << ' ';
        if (tmp->left) {
            que.enQueue(tmp->left);
        }
        if (tmp->right) {
            que.enQueue(tmp->right);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;

    cin >> N;
    bTree<int> Tree(N);
    for (int i = 1; i <= N; i++) {
        cin >> leftNum[i] >> rightNum[i] >> numNum[i];
    }

    for (int i = 1; i <= N; i++) {
        Tree.addNode(i, leftNum[i], numNum[i], 0);
        Tree.addNode(i, rightNum[i], numNum[i], 1);
    }

    Tree.findRoot();

    Tree.levelOrder();

    return 0;
}

yyong119's solution

#include <cstdio>
#include <queue>
using namespace std;

const int MAX_N = 100000;
struct node_data {
    int left_child, right_child, father, value;
} node[MAX_N + 10];

int main() {

    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int tmp_left, tmp_right, tmp_value; scanf("%d%d%d", &tmp_left, &tmp_right, &tmp_value);
        node[i].value = tmp_value;
        node[i].left_child = tmp_left; node[tmp_left].father = i;
        node[i].right_child = tmp_right; node[tmp_right].father = i;
    }

    int root = 1;
    while (node[root].father) root = node[root].father;
    queue<int> que; que.push(root);

    while (!que.empty()) {
        int tmp = que.front(); que.pop();
        printf("%d ", node[tmp].value);
        if (node[tmp].left_child) que.push(node[tmp].left_child);
        if (node[tmp].right_child) que.push(node[tmp].right_child);
    }

    return 0;
}