Untitled
unknown
plain_text
4 years ago
3.3 kB
5
Indexable
/* 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*/
Editor is loading...