Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
3.3 kB
3
Indexable
Never
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */

//只需繳交public function部分
#include <iostream>
using namespace std;

class TreeNode{
public:
    TreeNode(int, TreeNode*, TreeNode*);
    void add(TreeNode*);
    void search_num(int);
    void remove_num(TreeNode *tree);
    void PrePrint(); //print in Preorder
private:
    int value;
    TreeNode* left;
    TreeNode* right;
};

TreeNode::TreeNode(int val, TreeNode*r = NULL, TreeNode*l=NULL){
    value = val;
    left = l;
    right = r;
}

void TreeNode::add(TreeNode *tmp) {
    TreeNode *root = this;

    /*if(root==nullptr) {
        root = new TreeNode(tmp->value);
        cout<<"test";
        return;
    }*/

    while(root!=nullptr){
        if(tmp->value > root->value){
            if(root->right==nullptr)
                root->right = tmp;
            else
                root = root->right;
        }

        else if(root->value == tmp->value){
            return;
        }

        else{
            if(root->left==nullptr)
                root->left = tmp;
            else
                root = root->left;
        }

    }

}

void TreeNode::search_num(int num){
    TreeNode *root = this;

    while(root!=nullptr){
        if(root->value == num){
            cout<<"YES"<<endl;
            return;
        }
        else if(root->value < num)
            root = root->right;
        else
            root = root->left;
    }
    cout<<"NO"<<endl;
}

void TreeNode::remove_num(TreeNode *tree){
    TreeNode *tree = this;

    while(tree!=nullptr){
        if(tree->value == target->value)
            break;
        else if(tree->value < target->value)
            tree = tree->right;
        else
            tree = tree->left;
    }
    TreeNode *nodeToDelete = tree;

    TreeNode *attachPoint;
    if(tree->right==nullptr)
        tree = tree->left;
    else if(tree->left == nullptr)
        tree = tree->right;
    else{
        //the node has two children
        attachPoint = tree->right;
        while(attachPoint->left != nullptr){
            attachPoint = attachPoint->left;
        }
        attachPoint->left = tree->left;
        tree = tree->right;
    }
    delete nodeToDelete;

}

void TreeNode::PrePrint(){
    TreeNode *root  = this;

    if(root!=nullptr){
        cout<<root->value<<" ";
        root->left->PrePrint();
        root->right->PrePrint();
    }

}

int main(){
    TreeNode *root;
    char ch;
    int num;
    cin>>ch>>num;
    root = new TreeNode(num);
    while(cin>>ch) {
        if(ch=='E') break;

        switch(ch)
        {
            case 'A':
                {
                    cin>>num;
                    TreeNode *node = new TreeNode(num);
                    root->add(node);
                    break;
                }
            case 'S':
                {
                    cin>>num;
                    root->search_num(num);
                    break;
                }

            case 'D':
                {
                    cin>>num;
                    TreeNode *node = new TreeNode(num);
                    root->remove_num(node);
                    break;
                }

            case 'P':
                {
                     root->PrePrint();
                     break;
                }
        }
    }
}


/* PRESET CODE END - NEVER TOUCH CODE ABOVE*/