Skip to content

11257: 【原1257】圣诞树1

题目

题目描述

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

Description

圣诞节快到了,Dunphy一家需要一棵圣诞树。他们希望你按照他们的要求制作一棵圣诞树,并且在制作的过程中告诉他们一些树的信息。这棵树最开始只有一个结点作为根(默认根为1),接下来他们会要求你完成若干操作,操作的内容如下:

1:在一个叶子结点上加入左右儿子。输入为”1 a b c”,表示建立新结点b、c,并将b作为a的左儿子,c作为a的右儿子。若该操作合法则输出”Ok!”,并完成操作;若不合法则输出”Error!”,不完成该操作(不合法的情况包括a不在树中,a不是叶子结点,b已在树中,c已在树中,或b=c)。

2:查询一个结点的情况。输入为”2 a”,表示查询a结点的信息。若该操作合法则输出”F L R”三个数,分别表示a的父结点,a的左儿子以及a的右儿子(用0表示不存在的结点信息,具体见样例);若不合法则输出”Error!”,不输出其他信息(不合法的情况为a不在树中)。

3:将某个点与它的兄弟交换。输入为”3 a”,表示将a与它的兄弟交换。若该操作合法,则在树中将a的父结点的左右两棵子树交换,并输出a的兄弟结点;若不合法则输出”Error!”,不完成该操作(不合法的情况为a不在树中,或a=1)。

所有操作结束后,Dunphy一家还想知道整棵树的样子。因此你要告诉他们这棵树的先序遍历(根->左->右)。

Input Format

第一行为m,表示共m个操作。 接下来m行,每行一个操作。输入的格式一定合法,即不会出现类似”1 a b”或者”2 a b c”这样的情况。

所有的输入均为1~100000之间的整数。 有50%的数据m<=100。

Output Format

输出如题意描述。前m行对应m个操作的相应输出,最后一行为最后整棵树的先序遍历。

Sample Input

6
1 1 2 3
1 2 5 4
2 4
2 6
1 4 3 7
3 3

Sample Output

Ok!
Ok!
2 0 0
Error!
Error!
2
1 3 2 5 4

ligongzzz's solution

#include "iostream"
#include "queue"
#include "stack"
#include "cstdio"
using namespace std;

//二叉树类
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;
    }
    //创建结点全部完成后需要CheckRoot进行根节点识别
    void createNode(int nodeNum, int lchild, int rchild, T 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;
    }


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

    //迭代器
    class preorderIterator {
        stack<node*> myStack;
        node* currentData = nullptr;
        friend preorderIterator myBinaryTree::preorderBegin();
    public:
        T& get() {
            return currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr&&myStack.empty();
        }

        preorderIterator& operator++() {
            if (finish())
                return *this;
            if (myStack.empty()) {
                currentData = nullptr;
                return *this;
            }
            currentData = myStack.top();
            myStack.pop();
            if (currentData->rchild != nullptr)
                myStack.push(currentData->rchild);
            if (currentData->lchild != nullptr)
                myStack.push(currentData->lchild);
            return *this;
        }
    };

    preorderIterator preorderBegin() {
        preorderIterator result;
        result.myStack.push(root);
        ++result;
        return result;
    }
};

int main() {
    int opNum;
    cin >> opNum;
    myBinaryTree<int> bTree;
    bTree.createTree(100000);
    bTree.createNode(1, 0, 0, 1);
    bTree.root = bTree.nodeList[1];

    for (; opNum > 0; opNum--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            //判断是否合法
            if (bTree.nodeList[a] == nullptr ||
                bTree.nodeList[a]->lchild != nullptr || bTree.nodeList[a]->rchild != nullptr ||
                bTree.nodeList[b] != nullptr || bTree.nodeList[c] != nullptr) {
                printf("Error!\n");
                continue;
            }
            else {
                bTree.createNode(a, b, c, a);
                bTree.nodeList[b]->data = b;
                bTree.nodeList[c]->data = c;
                printf("Ok!\n");
            }
        }
        else if (op == 2) {
            int a;
            scanf("%d", &a);
            //判断是否合法
            if (bTree.nodeList[a] == nullptr) {
                printf("Error!\n");
                continue;
            }
            else {
                printf("%d %d %d\n",
                    bTree.nodeList[a]->parent == nullptr ? 0 : bTree.nodeList[a]->parent->data,
                    bTree.nodeList[a]->lchild == nullptr ? 0 : bTree.nodeList[a]->lchild->data,
                    bTree.nodeList[a]->rchild == nullptr ? 0 : bTree.nodeList[a]->rchild->data);
            }
        }
        else if (op == 3) {
            int a;
            scanf("%d", &a);
            //判断是否合法
            if (a == 1 || bTree.nodeList[a] == nullptr) {
                printf("Error!\n");
                continue;
            }
            else {
                auto father = bTree.nodeList[a]->parent;
                auto temp = father->lchild;
                father->lchild = father->rchild;
                father->rchild = temp;
                printf("%d\n", father->lchild == bTree.nodeList[a] ? father->rchild->data : father->lchild->data);
            }
        }
    }

    //输出
    bool firstWrite = true;
    for (auto p = bTree.preorderBegin(); !p.finish(); ++p) {
        if (firstWrite)
            firstWrite = false;
        else
            printf(" ");
        printf("%d", p.get());
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 100000;
class bTree {
   private:
    struct Node {
        int data;
        Node *parent;
        Node *left;
        Node *right;

        Node(int d, Node *p = NULL, Node *l = NULL, Node *r = NULL)
            : data(d), parent(p), left(l), right(r) {}
    };
    Node *nodes[maxN + 100] = {NULL};
    void clear(Node *n);
    void preOrder(Node *p) const;

   public:
    bTree();
    ~bTree();
    void add(int n, int a, int b);
    void find(int n);
    void change(int n);
    void preOrder() const;
};

bTree::bTree() {
    Node *tmp = new Node(1);
    nodes[1] = tmp;
}

bTree::~bTree() {
    // clear(nodes[1]);
}

void bTree::clear(Node *n) {
    nodes[n->data] = 0;
    if (n->left) {
        clear(n->left);
    }
    if (n->right) {
        clear(n->right);
    }
    delete n;
}

void bTree::add(int n, int a, int b) {
    if (nodes[n] == NULL || nodes[n]->left != NULL || nodes[n]->right != NULL ||
        nodes[a] != NULL || nodes[b] != NULL || a == b) {
        cout << "Error!" << '\n';
        return;
    }
    nodes[a] = new Node(a, nodes[n], 0, 0);
    nodes[b] = new Node(b, nodes[n], 0, 0);
    nodes[n]->left = nodes[a];
    nodes[n]->right = nodes[b];
    cout << "Ok!" << '\n';
}

void bTree::find(int n) {
    if (nodes[n] == NULL) {
        cout << "Error!" << '\n';
        return;
    }
    if (nodes[n]->parent == NULL) {
        cout << 0 << ' ';
    } else {
        cout << nodes[n]->parent->data << ' ';
    }
    if (nodes[n]->left == NULL) {
        cout << 0 << ' ';
    } else {
        cout << nodes[n]->left->data << ' ';
    }
    if (nodes[n]->right == NULL) {
        cout << 0 << ' ';
    } else {
        cout << nodes[n]->right->data << ' ';
    }
    cout << '\n';

    return;
}

void bTree::change(int n) {
    if (nodes[n] == NULL || n == 1) {
        cout << "Error!" << '\n';
        return;
    }

    Node *tmp = nodes[n]->parent, *lTmp = tmp->left;
    if (tmp->left == nodes[n]) {
        cout << tmp->right->data << '\n';
    } else {
        cout << tmp->left->data << '\n';
    }
    tmp->left = tmp->right;
    tmp->right = lTmp;

    return;
}

void bTree::preOrder() const { preOrder(nodes[1]); }

void bTree::preOrder(Node *p) const {
    if (p == NULL) {
        return;
    }
    cout << p->data << ' ';
    preOrder(p->left);
    preOrder(p->right);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, n, a, b, c;
    bTree tree1;

    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> n;
        if (n == 1) {
            cin >> a >> b >> c;
            tree1.add(a, b, c);
        } else if (n == 2) {
            cin >> a;
            tree1.find(a);
        } else if (n == 3) {
            cin >> a;
            tree1.change(a);
        }
    }
    tree1.preOrder();
    return 0;
}