Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
2.3 kB
3
Indexable
Never
//只需繳交public function部分  
#include <iostream>  
using namespace std;  
  
class TreeNode{  
public:  
    TreeNode(int, TreeNode*, TreeNode*);  
    void add(TreeNode *);  
    void PrePrint(); //print in Preorder 
	void Search(int ); 
	void Delete(int ,TreeNode** );
private:  
    int value;  
    TreeNode* left;  
    TreeNode* right;  
}; 
TreeNode::TreeNode(int v, TreeNode *l, TreeNode *r){
	value = v;
	left = l;
	right = r;
}
void TreeNode::add(TreeNode *ptr){
	if( value < ptr->value ){
		if(right != NULL){
			right->add(ptr);
		}else{
			right=ptr;
		}
	}
	else if( ptr->value < value ){
		if(left != NULL){
			left->add(ptr);
		}else{
			left=ptr;
		}
	}
}
void TreeNode::PrePrint(){ //print in Preorder
	cout<<value<<" ";
	if(left!=NULL){
		left->PrePrint();
	}
	if(right!=NULL){
		right->PrePrint();
	}
}
void TreeNode::Search(int x){
	if(value < x){
		if(right != NULL){
			right->Search(x);
		}else{
			cout<<"NO"<<endl;
		}
	}
	else if(x < value){
		if(left != NULL){
			left->Search(x);
		}else{
			cout<<"NO"<<endl;
		}
	}
	else if(value == x){
		cout<<"YES"<<endl;
	}
}
void TreeNode::Delete(int x,TreeNode **pre){
	//pre 指向此值的pointer 
	TreeNode *ptr=*pre;
	if(value == x){
		if( right==NULL && left==NULL ){
			*pre = NULL;
		}
		else if( right==NULL ){
			*pre = left;
		}
		else if( left==NULL ){
			*pre = right;
		}
		else if( right!=NULL && left!=NULL ){
			*pre = right;
			TreeNode *left_ptr=right;
			while( left_ptr->left!=NULL ){
				left_ptr = left_ptr->left;
			}
			if(left_ptr){
				left_ptr->left=left;
			}
		}
		delete ptr;
	}
	else if(value < x){
		right->Delete(x,&right);
	}
	else if(x < value){
		left->Delete(x,&left);
	}
}
int main(){  
	char c;
	int value=0;
	TreeNode *root=NULL;
    while(cin>>c){
    	if(c=='A'){
    		cin >> value;
			TreeNode* node = new TreeNode(value, NULL, NULL);
    		if(root == NULL){
    			root=node;
			}else{
	        	root->add(node);
			}
		}
		else if(c=='S'){
			cin>>value;
			root->Search(value);
		}
		else if(c=='D'){
			cin>>value;
			root->Delete(value,&root);
			if(root==NULL)
				cout<<"wrong"<<endl;
		}
		else if(c=='P'){
			root->PrePrint();
			cout<<endl;
		}
		else if(c=='E'){
			break;
		}
	}  
}