# 11212: 【原1212】levelOrder

### 题目描述

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

## 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
``````

## 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;
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.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();
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>
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 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.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;
}
``````