Skip to content

11214: 【原1214】traverse

题目

题目描述

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

Description

给出一棵孩子兄弟表示法下的树的结构以及各个结点的权值,要求按先序、后序、层次遍历二叉树并输出各个结点的权值。

Input Format

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

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

第二行到第N+1行,每行包含三个整数,代表一个节点,序号为 1 的节点在这 N 行中的第 1 行(不包括节点总数那一行)。其中第i行的三个整数Pi,Qi,Vi,代表序号为 i 的节点左孩子序号为Pi,右兄弟序号为Qi,序号为 i 的结点自身的权值为Vi。若Pi=0,则表明结点i没有左孩子。同样的,若Qi=0,则表明i节点没有右兄弟。(ps. 第i行指的是这N行中的第i行)

Output Format

输出包含三行。

第一行包含N个数,表示按先序遍历输出的各个结点的权值,用一个空格隔开。

第二行包含N个数,表示按后序遍历输出的各个结点的权值,用一个空格隔开。

第三行包含N个数,表示按层次遍历输出的各个结点的权值,用一个空格隔开。

Sample Input

9
2 0 111
5 3 222
0 4 333
7 0 444
0 6 555
0 0 666
0 8 777
0 9 888
0 0 999

Sample Output

111 222 555 666 333 444 777 888 999
555 666 222 333 777 888 999 444 111
111 222 333 444 555 666 777 888 999

Limit

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

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

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

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/31.
//

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

template<typename Item>
class Queue {
    class Node {
    public:
        Item item;
        Node *next = nullptr;
    };

    int N;
    Node *first;
    Node *last;

public:
    Queue() {
        N = 0;
        first = last = nullptr;
    }

    bool isEmpty() const {
        return N == 0;
    }

    int size() const {
        return N;
    }

    void enqueue(Item item) {
        if (N == 0) {
            first = new Node{item};
            last = first;
        } else {
            Node *tmp = last;
            last = new Node{item};
            tmp->next = last;
        }
        ++N;
    }

    Item dequeue() {
        Item item = first->item;
        Node *tmp = first;
        first = first->next;
        if (N == 1) last = nullptr;
        delete tmp;
        --N;
        return item;
    }

    Item getFirst() const {
        return first->item;
    }

    Item getLast() const {
        return last->item;
    }

    void clear() {
        Node *tmp;
        while (first != nullptr) {
            tmp = first;
            first = first->next;
            delete tmp;
        }
        N = 0;
        first = last = nullptr;
    }

    void print(ostream &os = std::cout) const {
        Node *p = first;
        while (p) {
            os << p->item << ' ';
            p = p->next;
        }
        os << endl;
    }

    virtual ~Queue() {
        Node *tmp;
        while (first != nullptr) {
            tmp = first;
            first = first->next;
            delete tmp;
        }
    }
};

template<typename Item>
class BinaryTree {

    class Node {
    public:
        Node *left = nullptr, *bro = nullptr;
        Node *father = nullptr;
        Item val;
    };

    int size;
    int maxSize;
    Node *root;
    Node **nodes;

    Queue<Item> pre;
    Queue<Item> post;
    Queue<Item> level;

private:
    void dfs(Node *node) {
        pre.enqueue(node->val);
        if (node->left) dfs(node->left);
        post.enqueue(node->val);
        if (node->bro) dfs(node->bro);
    }

    void bfs() {
        Queue<Node *> queue;
        queue.enqueue(root);

        Node *p;
        while (!queue.isEmpty()) {
            p = queue.dequeue();
            while (p) {
                level.enqueue(p->val);
                if (p->left)
                    queue.enqueue(p->left);
                p = p->bro;
            }
        }
    }

public:
    BinaryTree() {
        BinaryTree(5);
    }

    explicit BinaryTree(int maxSize) {
        root = nullptr;
        this->maxSize = maxSize;
        nodes = new Node *[maxSize + 1]{};
        for (int i = 1; i <= maxSize; ++i) {
            nodes[i] = new Node();
        }
        size = 0;
    }

    void add(int left, int bro, Item item) {
        if (size == maxSize) resize(maxSize * 2);
        ++size;

        nodes[size]->val = item;
        nodes[size]->left = nodes[left];
        nodes[size]->bro = nodes[bro];
        if (left) nodes[left]->father = nodes[size];
        if (bro) nodes[bro]->father = nodes[size];
    }

    void resize(int newSize) {
        auto oldNodes = nodes;
        nodes = new Node *[newSize + 1]{};
        for (int i = 1; i <= maxSize; ++i) {
            nodes[i] = oldNodes[i];
        }
        for (int i = maxSize + 1; i <= newSize; ++i) {
            nodes[i] = new Node;
        }
        maxSize = newSize;
    }

    void getRoot() {
        Node *p = nodes[1];
        while (p->father) {
            p = p->father;
        }
        root = p;
    }

    void traverse() {
        getRoot();
        pre.clear();
        post.clear();
        level.clear();

        dfs(root);
        bfs();
    };

    const Queue<Item> &getPre() {
        return pre;
    }

    const Queue<Item> &getPost() {
        return post;
    }

    const Queue<Item> &getLevel() {
        return level;
    }

    virtual ~BinaryTree() {
        for (int i = 1; i <= maxSize; ++i) {
            delete nodes[i];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    BinaryTree<int> binaryTree(N);
    int a, b, c;
    while (N--) {
        cin >> a >> b >> c;
        binaryTree.add(a, b, c);
    }

    binaryTree.traverse();
    binaryTree.getPre().print();
    binaryTree.getPost().print();
    binaryTree.getLevel().print();

    return 0;
}

FineArtz's solution

/* traverse */
#include <iostream>
using namespace std;

struct Node{
    int child = 0, sibling = 0;
    int val = 0;
};

Node a[100005];
bool b[100005] = {0};
int n;

void foretra(int x){
    if (x == 0)
        return;
    cout << a[x].val << ' ';
    int t = a[x].child;
    while (t){
        foretra(t);
        t = a[t].sibling;
    }
}

void backtra(int x){
    if (x == 0)
        return;
    int t = a[x].child;
    while (t){
        backtra(t);
        t = a[t].sibling;
    }
    cout << a[x].val << ' ';
}

void hieatra(int root){
    int q[100005];
    int front = 0, rear = 0;
    q[rear++] = root;
    while (front != rear){
        int now = q[front];
        front++;
        cout << a[now].val << ' ';
        int t = a[now].child;
        while (t){
            q[rear++] = t;
            t = a[t].sibling;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].child >> a[i].sibling >> a[i].val;
        b[a[i].child] = true;
        b[a[i].sibling] = true;
    }
    int root = 0;
    for (int i = 1; i <= n; ++i){
        if (!b[i]){
            root = i;
            break;
        }
    }
    foretra(root);
    cout << '\n';
    backtra(root);
    cout << '\n';
    hieatra(root);
    cout << '\n';
    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 mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[size];
        vector_data[size--] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

//二叉树类
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;
    }

    //层次遍历
    mVector<T> levelTraversal() {
        if (sizeOfTree == 0)
            return *new mVector<T>;

        mVector<T> result; 
        mQueue<node*> treeQueue;

        //根结点入队
        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.push_back(temp->data);
        }

        //返回
        return result;
    }

    //前序遍历
    mVector<T> preorderTraversal() {
        mVector<T> result;
        preorderTraversal(root, result);
        return result;
    }

    void preorderTraversal(node* treeRoot,mVector<T> &result) {
        //显示当前
        result.push_back(treeRoot->data);

        if (treeRoot->lchild != nullptr)
            preorderTraversal(treeRoot->lchild,result);
        if (treeRoot->rchild != nullptr)
            preorderTraversal(treeRoot->rchild,result);
    }

    //中序遍历
    mVector<T> midorderTraversal() {
        mVector<T> result;
        midorderTraversal(root, result);
        return result;
    }

    void midorderTraversal(node* treeRoot, mVector<T> &result) {
        if (treeRoot->lchild != nullptr)
            midorderTraversal(treeRoot->lchild, result);
        //显示当前
        result.push_back(treeRoot->data);
        if (treeRoot->rchild != nullptr)
            midorderTraversal(treeRoot->rchild, result);
    }

    //后序遍历
    mVector<T> lostorderTraversal() {
        mVector<T> result;
        lostorderTraversal(root, result);
        return result;
    }

    void lostorderTraversal(node* treeRoot, mVector<T> &result) {
        if (treeRoot->lchild != nullptr)
            lostorderTraversal(treeRoot->lchild, result);
        if (treeRoot->rchild != nullptr)
            lostorderTraversal(treeRoot->rchild, result);
        //显示当前
        result.push_back(treeRoot->data);
    }
};

//左孩子右兄弟二叉树类
template <class T>
class mySpecialBinaryTree {
public:
    class node {
    public:
        T data;
        node *lchild = nullptr, *rbrother = nullptr;
        bool isRoot = true;
    };
    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 rbrother, 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]->isRoot = false;
            nodeList[nodeNum]->lchild = nodeList[lchild];
        }

        if (rbrother != 0) {
            if (nodeList[rbrother] == nullptr)
                nodeList[rbrother] = new node;
            nodeList[rbrother]->isRoot = false;
            nodeList[nodeNum]->rbrother = nodeList[rbrother];
        }
    }

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

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

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

    //构造
    mySpecialBinaryTree() {}

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

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

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

    //层次遍历
    mVector<T> levelTraversal() {
        if (sizeOfTree == 0)
            return *new mVector<T>;

        mVector<T> result;
        mQueue<node*> treeQueue;

        //根结点入队
        treeQueue.push(root);

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

            //入队
            for (auto p = temp->lchild; p!= nullptr; p = p->rbrother)
                treeQueue.push(p);

            //写入
            result.push_back(temp->data);
        }

        //返回
        return result;
    }

    //前序遍历
    mVector<T> preorderTraversal() {
        mVector<T> result;
        preorderTraversal(root, result);
        return result;
    }

    void preorderTraversal(node* treeRoot, mVector<T> &result) {
        //显示当前
        result.push_back(treeRoot->data);

        if (treeRoot->lchild != nullptr)
            preorderTraversal(treeRoot->lchild, result);
        if (treeRoot->rbrother != nullptr)
            preorderTraversal(treeRoot->rbrother, result);
    }

    //后序遍历
    mVector<T> lostorderTraversal() {
        mVector<T> result;
        lostorderTraversal(root, result);
        return result;
    }

    void lostorderTraversal(node* treeRoot, mVector<T> &result) {
        if (treeRoot->lchild != nullptr)
            lostorderTraversal(treeRoot->lchild, result);
        //显示当前
        result.push_back(treeRoot->data);
        if (treeRoot->rbrother != nullptr)
            lostorderTraversal(treeRoot->rbrother, result);
    }
};

int main() {
    int num;
    mySpecialBinaryTree<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.preorderTraversal();

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

    cout << endl;

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

    auto ans2 = bTree.levelTraversal();

    cout << endl;

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

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 100000;
int leftNum[maxN + 100] = {0}, rightNum[maxN + 100] = {0};
long long int 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 *leftSon;
        Node *leftBrother;
        Node *rightBrother;
        Node *parent;

        Node(T d = 0)
            : data(d), parent(0), leftSon(0), leftBrother(0), rightBrother(0) {}
    };
    Node *root;
    Node *nodes[maxN + 100];
    void clear(Node *);
    void preOrder(Node *) const;
    void postOrder(Node *) const;

   public:
    bTree(int n = 10);
    ~bTree();
    void addNode(int, int, T, bool);
    void findRoot();
    void levelOrder() const;
    void preOrder() const;
    void postOrder() 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->leftSon);
    clear(p->rightBrother);
    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]->leftSon = nodes[i];
    } else if (i != 0 && isRight) {
        nodes[i]->leftBrother = nodes[n];
        nodes[n]->rightBrother = nodes[i];
    }
    nodes[n]->data = x;
}

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

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

    cout << root->data << ' ';
    que.enQueue(root);
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        tmp1 = tmp->leftSon;
        while (tmp1) {
            cout << tmp1->data << ' ';
            que.enQueue(tmp1);
            tmp1 = tmp1->rightBrother;
        }
    }
}

template <class T>
void bTree<T>::preOrder(Node *t) const {
    cout << t->data << ' ';

    Node *tmp = t;
    while (tmp->rightBrother != 0 && t == root) {
        preOrder(tmp->rightBrother);
        tmp = tmp->rightBrother;
    }

    if (t->leftSon != 0) {
        preOrder(t->leftSon);
        Node *tmp1 = t->leftSon;
        while (tmp1->rightBrother != 0) {
            preOrder(tmp1->rightBrother);
            tmp1 = tmp1->rightBrother;
        }
    }
}

template <class T>
void bTree<T>::postOrder(Node *t) const {
    Node *tmp = t;
    while (tmp->rightBrother != 0 && t == root) {
        postOrder(tmp->rightBrother);
        tmp = tmp->rightBrother;
    }

    if (t->leftSon != 0) {
        postOrder(t->leftSon);

        Node *tmp1 = t->leftSon;
        while (tmp1->rightBrother != 0) {
            postOrder(tmp1->rightBrother);
            tmp1 = tmp1->rightBrother;
        }
    }
    cout << t->data << ' ';
}

template <class T>
void bTree<T>::preOrder() const {
    preOrder(root);
}

template <class T>
void bTree<T>::postOrder() const {
    postOrder(root);
}

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

    int N;

    cin >> N;
    bTree<long long 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);
    }
    for (int i = 1; i <= N; i++) {
        Tree.addNode(i, rightNum[i], numNum[i], 1);
    }

    Tree.findRoot();

    Tree.preOrder();
    cout << '\n';
    Tree.postOrder();
    cout << '\n';
    Tree.levelOrder();

    return 0;
}

q4x3's solution

/**
 * 树的前序后序遍历
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

const int MAXN = 1e5 + 233;
int l[MAXN], r[MAXN], val[MAXN], vis[MAXN], q[MAXN << 1]; 
int N, rt;

void pre(int rt) {
    printf("%d ", val[rt]);
    int son = l[rt];
    if(!son) return;
    while(1) {
        pre(son);
        son = r[son];
        if(son == 0) break;
    }
    return;
}

void pos(int rt) {
    int son = l[rt];
    if(!son) {
        printf("%d ", val[rt]);
        return;
    }
    while(1) {
        pos(son);
        son = r[son];
        if(son == 0) break;
    }
    printf("%d ", val[rt]);
    return;
}

void seq() {
    int head = 0, rear = 0;
    q[rear ++] = rt;
    while(head != rear) {
        int top = q[head];
        printf("%d ", val[top]);
        ++ head;
        int son = l[top];
        while(1) {
            if(!son) break;
            q[rear ++] = son;
            son = r[son];
        }
    }
}

int main() {
    scanf("%d", &N);
    for(int i = 1;i <= N;++ i) {
        scanf("%d%d%d", &l[i], &r[i], &val[i]);
        vis[l[i]] = 1;
        vis[r[i]] = 1;
    }
    for(int i = 1;i <= N;++ i) {
        if(!vis[i]) {
            rt = i;
            break;
        }
    }
    pre(rt); putchar('\n');
    pos(rt); putchar('\n');
    seq(); putchar('\n');
}

skyzh's solution

#include <iostream>

using namespace std;

template <typename T>
struct Node {
    T x;
    int l, sibling;
    Node() : l(0), sibling(0) {}
    Node(const T& x, int l = 0, int r = 0) : x(x), l(l), sibling(r) {}
};

template <typename T>
struct Tree {
    Node <T> *nodes;
    Tree(int cap) : nodes(new Node<T> [cap]) {}
    ~Tree() { delete [] nodes; }
};

Tree <int> tree(100001);
bool is_child[100001] = { 0 };

void pre_traverse(const Tree<int> & tree, int node) {
    if (node == 0) return;
    const Node<int> &ptr = tree.nodes[node];
    printf("%d ", ptr.x);
    pre_traverse(tree, ptr.l);
    pre_traverse(tree, ptr.sibling);
}

void post_traverse(const Tree<int> & tree, int node) {
    if (node == 0) return;
    const Node<int> &ptr = tree.nodes[node];
    post_traverse(tree, ptr.l);
    printf("%d ", ptr.x);
    post_traverse(tree, ptr.sibling);
}

template <typename T>
struct Queue {
    T* d;
    int f, r;
    Queue(int cap) : d(new T[cap]), f(0), r(0) {}
    bool empty() { return f == r; }
    void enqueue(const T& x) { d[r++] = x; }
    const T dequeue() { return d[f++]; }
    ~Queue() { delete[] d; }
};

void level_traverse(const Tree<int> & tree, int root) {
    if (root == 0) return;
    Queue <int> q(300000);
    q.enqueue(root);
    while (!q.empty()) {
        const Node<int>& node = tree.nodes[q.dequeue()];
        printf("%d ", node.x);
        if (node.l != 0) {
            q.enqueue(node.l);
            int ptr = tree.nodes[node.l].sibling;
            while (ptr) {
                q.enqueue(ptr);
                ptr = tree.nodes[ptr].sibling;
            }
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d%d", &tree.nodes[i].l, &tree.nodes[i].sibling, &tree.nodes[i].x);
        is_child[tree.nodes[i].l] = is_child[tree.nodes[i].sibling] = true;
    }
    int root = 0;
    for (int i = 1; i <= N; i++) {
        if (!is_child[i]) root = i;
    }
    pre_traverse(tree, root);
    printf("\n");
    post_traverse(tree, root);
    printf("\n");
    level_traverse(tree, root);
    printf("\n");
    return 0;
}

victrid's solution

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

struct tree {
    tree* left;
    tree* brat;
    int weight;
    bool isroot;
    tree() : left(nullptr), brat(nullptr), weight(0), isroot(true){};
};

tree seq[1000002] = {};

//pretrav
bool pretrav_f = false;
void pretrav(tree* root) {
    if (pretrav_f)
        printf(" ");
    pretrav_f = true;
    printf("%d", root->weight);
    if (root->left != nullptr)
        pretrav(root->left);
    if (root->brat != nullptr)
        pretrav(root->brat);
    return;
}

//posttrav
bool posttrav_f = false;
void posttrav(tree* root) {
    if (root->left != nullptr)
        posttrav(root->left);
    if (posttrav_f)
        printf(" ");
    posttrav_f = true;
    printf("%d", root->weight);
    if (root->brat != nullptr)
        posttrav(root->brat);
    return;
}

//bfstrav
tree* datastorage[1000003] = {nullptr};
tree** frontptr;
tree** endptr;
void clearqueue() {
    frontptr = datastorage;
    endptr   = datastorage + 1;
}
void clearstack() {
    endptr = datastorage;
}
void enqueue(tree* cr) {
    *endptr = cr;
    endptr++;
}
bool qempty() {
    return frontptr + 1 == endptr;
}
void enstack(tree* cr) {
    *endptr = cr;
    endptr++;
}
tree* destack() {
    if (endptr == datastorage)
        return nullptr;
    else
        endptr--;
    return *endptr;
}
tree* dequeue() {
    if (frontptr + 1 == endptr)
        return nullptr;
    else
        frontptr++;
    return *frontptr;
}
bool bfstrav_f = false;
void bfstrav(tree* root) {
    clearqueue();
    enqueue(root);
    while (!qempty()) {
        tree* rt = dequeue();
        while (rt != nullptr) {
            if (bfstrav_f)
                printf(" ");
            bfstrav_f = true;
            printf("%d", rt->weight);
            if (rt->left != nullptr)
                enqueue(rt->left);
            rt = rt->brat;
        }
    }
    return;
}
int main() {
    int t, l, b, vl, root;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        scanf("%d %d %d", &l, &b, &vl);
        if (l != 0) {
            seq[i].left         = seq + l;
            seq[i].left->isroot = false;
        }
        if (b != 0) {
            seq[i].brat         = seq + b;
            seq[i].brat->isroot = false;
        }
        seq[i].weight = vl;
    }
    for (int i = 1; i <= t; i++)
        if (seq[i].isroot) {
            root = i;
            break;
        }
    pretrav(seq + root);
    printf("\n");
    posttrav(seq + root);
    printf("\n");
    bfstrav(seq + root);
    printf("\n");

    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int n,l[200000],r[200000],v[200000],s[200000],root,queue[200000],head=0,tail=1,p;
void pre(int x){
    cout<<v[x]<<" ";
    int p=l[x];
    while (p) {pre(p); p=r[p];}
}
void post(int x){
    int p=l[x];
    while (p) {post(p); p=r[p];}
    cout<<v[x]<<" ";
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%d%d%d",&l[i],&r[i],&v[i]);
        s[l[i]]=1;
        s[r[i]]=1;
    }
    for (int i=1;i<=n;++i)
        if (!s[i]) root=i;
    pre(root);
    cout<<endl;
    post(root);
    cout<<endl;
    queue[0]=root;
    while (head<tail){
        cout<<v[queue[head]]<<" ";
        p=l[queue[head++]];
        while (p) {
            queue[tail++]=p;
            p=r[p];
        }
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 100010;
struct node {
    int lson = 0, rbro = 0, value = 0;
};
node a[MAX_N];

void preorder(int t) {

    cout << a[t].value << " ";
    if (a[t].lson) preorder(a[t].lson);
    if (a[t].rbro) preorder(a[t].rbro);
}

void postorder(int t) {

    if (a[t].lson) postorder(a[t].lson);
    cout << a[t].value << " ";
    if (a[t].rbro) postorder(a[t].rbro);
}

void level(queue<int> t) {

    queue<int> next;
    while (!next.empty()) next.pop();
    while (!t.empty()) {
        int temp = t.front();
        t.pop(); cout << a[temp].value << " ";
        if (a[temp].lson) {
            next.push(a[temp].lson);
            int temp2 = a[a[temp].lson].rbro;
            while (temp2) {
                next.push(temp2);
                temp2 = a[temp2].rbro;
            }
        }
    }
    if (!next.empty()) level(next);
}

int main() {

    ios::sync_with_stdio(false);
    int n; cin >> n;
    int pre[MAX_N]; memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; ++i) {
        int temp, lson, rbro;
        cin >> lson >> rbro >> temp;
        a[i].lson = lson;
        a[i].rbro = rbro;
        a[i].value = temp;
        pre[lson] = i;
        if (rbro) {
            pre[rbro] = pre[i] = -1;
        }
    }
    int root;
    for (root = 1; root <= n; ++root) if (pre[root] == 0) break;

    preorder(root);
    cout << endl;
    postorder(root);
    cout << endl;
    queue<int> p; p.push(root);
    level(p);
    cout << endl;
    return 0;
}

Zsi-r's solution

#include <iostream>

using namespace std;
//树的后根遍历 == 二叉树的中序遍历
//树的先根遍历 == 二叉树的先序遍历

class node
{
public:
    int data = NULL;
    int lchild = 0, brother = 0;
    node() {};
    node(int d, int l, int b) : data(d), lchild(l), brother(b){};
    node(node &x) { data = x.data, lchild = x.lchild, brother = x.brother; }
    ~node(){};
};

class linkQueue
{
    private:
    struct nodeInQueue{
        node data;
        nodeInQueue *next;
        nodeInQueue (const node &x, nodeInQueue *N = NULL)
        {
            data=x;next=N;
        }
        nodeInQueue() : next(NULL) {};
        ~nodeInQueue() {};
    };

    nodeInQueue *front,*rear;//队不空时front和rear都有数据当队长为1时front和rear所指相同

    public:
    linkQueue();
    ~linkQueue();
    bool isEmpty()const ;
    void enQueue(const node &x);
    node deQueue();
};

linkQueue::linkQueue()
{
    front = rear = NULL;
}

linkQueue::~linkQueue()
{
    nodeInQueue *tmp;
    while(front != NULL)
    {
        tmp = front;
        front = front ->next;
        delete tmp;
    }
}

bool linkQueue::isEmpty()const
{
    return front == NULL;
}

void linkQueue::enQueue(const node &x)
{
    if (rear == NULL) front = rear = new nodeInQueue (x);
    else 
        rear=rear->next=new nodeInQueue (x);
}

node linkQueue::deQueue()
{
    nodeInQueue *tmp=front;
    node value = front ->data;
    front = front ->next;
    if (front==NULL)rear=NULL;
    delete tmp;
    return value;
}


void pre(int accessnow,node*tree) 
{
    cout << tree[accessnow].data << " ";
    if (tree[accessnow].lchild != 0)
        pre(tree[accessnow].lchild-1, tree);
    if (tree[accessnow].brother != 0)
        pre(tree[accessnow].brother-1, tree);
    return;
}

void post(int accessnow,node*tree) 
{
    if (tree[accessnow].lchild != 0)
        post(tree[accessnow].lchild-1, tree);

    cout << tree[accessnow].data << " ";

    if (tree[accessnow].brother != 0)
        post(tree[accessnow].brother-1, tree);
    return;
}

void level(linkQueue &s,node *tree){
    node temp;
    while (!s.isEmpty()){
        temp = s.deQueue();
        if (temp.lchild!=0)
            s.enQueue(tree[temp.lchild-1]);
        cout << temp.data << ' ';
        while(temp.brother!=0){
            temp = tree[temp.brother-1];
            cout << temp.data << ' ';
            if (temp.lchild!=0)
                s.enQueue(tree[temp.lchild-1]);
        }
    }
}

int main()
{
    int NumNode;
    cin >> NumNode;
    node *tree = new node[NumNode];
    linkQueue que;

    int RootLine;
    bool *FindRoot = new bool[NumNode+1];
    for (int i = 0; i < NumNode + 1;i++)
        FindRoot[i] = false;

    for (int i = 0; i < NumNode;i++)
    {
        cin >> tree[i].lchild >> tree[i].brother >> tree[i].data;
        FindRoot[tree[i].lchild] = true;
        FindRoot[tree[i].brother] = true;
    }

    for (RootLine = 1; RootLine < NumNode + 1;RootLine ++)
    {
        if (!FindRoot[RootLine])
            break;
    }

    pre(RootLine-1, tree);
    cout << endl;
    post(RootLine-1, tree);

    que.enQueue(tree[RootLine-1]);

    cout << endl;
    level(que, tree);
    return 0;
}