11039: 【原1039】顺序存储二叉树

题目

题目描述

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

Description

用顺序存储实现二叉树。读入一棵二叉树，输出后序遍历的结果。

Input Format

第一行，一个整数 n，表示这棵树有 n 个节点。这 n 个节点编号为 1 到 n。

接下来 n 行，描述每个节点的左右儿子情况。每行包含三个整数 x y z，表示编号为 x 的节点的左儿子编号为 y，右儿子编号为 z。若 y=-1 或 z=-1，表示 x 没有左子树或右子树。

编号为 1 的节点为树的根节点。

Output Format

第一行：输出 n 个整数，第 i 个整数为编号 i 的节点在顺序存储的数组中的下标。输出的数之间用一个空格隔开。

第二行：输出这个树的后序遍历的结果，输出的数之间用空格隔开。

Hint

N<=30000，树的高度保证不超过15。

输入中，除了根节点外，每个节点的描述总在它的父节点的描述出现之后给出。

Sample Input

5
1 2 4
4 5 -1
5 -1 -1
2 -1 3
3 -1 -1

Sample Output

1 2 5 3 6
3 2 5 4 1

FineArtz's solution

/* 顺序存储二叉树 */
#include <iostream>
using namespace std;

class Node{
public:
    int l = 0, r = 0, pos = 0, ind = 0;
};

Node a[100005];
int n, root = 0, b[100005], c[100005];

void encode(int root){
    int q[200005], front = 0, rear = 0, cnt = 0, r = 0;
    q[rear++]= root;
    r = rear;
    a[root].pos = ++cnt;
    while (front != r){
        int now = q[front++];
        ++cnt;
        if (now != -1){
            if (a[now].l != -1){
                q[rear++] = b[a[now].l];
                a[b[a[now].l]].pos = cnt;
                r = rear;
            }
            else
                q[rear++] = -1;
        }
        else{
            q[rear++] = -1;
        }
        ++cnt;
        if (now != -1){
            if (a[now].r != -1){
                q[rear++] = b[a[now].r];
                a[b[a[now].r]].pos = cnt;
                r = rear;
            }
            else
                q[rear++] = -1;
        }
        else{
            q[rear++] = -1;
        }
    }
    for (int i = 1; i <= n; ++i){
        c[a[i].ind] = a[i].pos;
    }
    for (int i = 1; i <= n; ++i)
        cout << c[i] << ' ';
    cout << endl;
}

void sufTrans(int x){
    if (a[x].l != -1)
        sufTrans(b[a[x].l]);
    if (a[x].r != -1)
        sufTrans(b[a[x].r]);
    cout << a[x].ind << ' ';
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].ind >> a[i].l >> a[i].r;
        if (a[i].ind == 1)
            root = i;
    }
    for (int i = 1; i <= n; ++i){
        b[a[i].ind] = i;
    }
    encode(root);
    sufTrans(root);
    cout << endl;
    return 0;
}

ligongzzz's solution

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


int fuck_data[30009] = { 0 };
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 != -1) {
            if (nodeList[lchild] == nullptr)
                nodeList[lchild] = new node;
            nodeList[lchild]->parent = nodeList[nodeNum];
            nodeList[nodeNum]->lchild = nodeList[lchild];
        }

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

    void checkRoot() {
        root = nodeList[1];
        fuck_data[1] = 1;
        get_fuck(1);
    }

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

    void get_fuck(int pos) {
        if (nodeList[pos]->lchild) {
            fuck_data[nodeList[pos]->lchild->data] = fuck_data[pos] * 2;
            get_fuck(nodeList[pos]->lchild->data);
        }
        if (nodeList[pos]->rchild) {
            fuck_data[nodeList[pos]->rchild->data] = fuck_data[pos] * 2 + 1;
            get_fuck(nodeList[pos]->rchild->data);
        }
    }

    //层次遍历
    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> 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);
    }
};



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

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

    bTree.checkRoot();
    cout << fuck_data[1];
    for (int i = 2; i <= num; ++i)
        cout << " " << fuck_data[i];
    cout << endl;
    auto ans = bTree.lostorderTraversal();
    for (auto p : ans)
        cout << p << " ";

    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int n,root,postn,seq[30001],post[30001],ls[30001],rs[30001],x,y,z;
void dfs(int x)
{
    if (ls[x]!=-1) {
        seq[ls[x]]=2*seq[x];
        dfs(ls[x]);
    }
    if (rs[x]!=-1){
        seq[rs[x]]=2*seq[x]+1;
        dfs(rs[x]);
    }
    post[++postn]=x;
}
int main() {
    cin>>n;
    for (int i=0;i<n;++i){
        cin>>x>>y>>z;
        if (i==0) root=x;
        ls[x]=y;
        rs[x]=z;
    }
    seq[root]=1;
    dfs(root);
    for (int i=1;i<=n;++i)
        cout<<seq[i]<<" ";
    cout<<endl;
    for (int i=1;i<=n;++i)
        cout<<post[i]<<" ";
    return 0;
}

yyong119's solution

#include <iostream>
using namespace std;
const int MAX_N = 30010;
struct node {
    int lson = -1, rson = -1;
}a[MAX_N];
int num[MAX_N];

void findnum(int node, int nodenum) {

    if (a[node].lson != -1) findnum(a[node].lson, nodenum << 1);
    if (a[node].rson != -1) findnum(a[node].rson, nodenum << 1 | 1);
    num[node] = nodenum;
}

void output(int node) {

    if (a[node].lson != -1) output(a[node].lson);
    if (a[node].rson != -1) output(a[node].rson);
    cout << node << " ";
}
int main() {

    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        int temp, l, r;
        cin >> temp >> l >> r;
        a[temp].lson = l; a[temp].rson = r;
    }
    num[1] = 1;
    findnum(1, 1);
    for (int i = 1; i <= n; ++i) cout << num[i] << " ";
    cout << endl;
    output(1);
    return 0;
}