#include<iostream>
#define N 100

using namespace std;

struct TreeNode{
        
     int value;   
     TreeNode *left;
     TreeNode *right; 
     
       
        }; 



struct Queue{
        TreeNode queuearray[N];
        int rear;
        int front;
        
        
        };
Queue q;


int isEmpty(Queue *);   
void BST_insert(int,TreeNode **);
void queueMove(Queue *);
void levelOrder(TreeNode *);
void preorder(TreeNode *);
void inorder(TreeNode *);
void postorder(TreeNode *);
TreeNode* BST_delete(TreeNode *,int);
void createQueue(Queue *);
        
int main(void){
        
        
        
       int data;
       TreeNode *root=NULL;
       
       int choose,loopflag=1;
        
    while(loopflag){
            
		cout << "\n(1)插入節點\n(2)Level Order列出樹中所有節點\n(3)前序追蹤\n(4)中序追蹤\n(5)後序追蹤\n(6)刪除一元素\n(0)結束 => ";
		cin >> choose;        
       switch(choose){
        case 0:   
             loopflag=0;
             break;      
        case 1:   
             
             cout << "請輸入欲放入之資料=> ";
			 cin >> data;
             BST_insert(data,&root);      
             break;
        case 2:
             levelOrder(root);
             break;
        case 3:
             preorder(root);
             break;
        case 4:
             inorder(root);
             break;
        case 5:
             postorder(root);
             break;
        case 6:
             cin>>data;
             BST_delete(root,data);
             break;         
         default:
                 cout<<"輸入錯誤"<<endl;    
                 break;
                      
                      
                      }             
                    
                    
                    
                    
                    }

     
     return 0;
    
    
}


void BST_insert(int x,TreeNode **root){
     TreeNode  *q=*root,*r=NULL;
     
     while(q!=NULL){
              r=q;
              if(x<q->value)
              q=q->left;
              else
              q=q->right;      
                    }
                    
                    
       q=new TreeNode;
       
       q->value=x;
       q->left=NULL;
       q->right=NULL;
       if(r==NULL)
       *root=q;
       else if(x<r->value)
       r->left=q;
       else
       r->right=q;
     
     }
     
void createQueue(Queue *p){
     p->rear=-1;
     p->front=-1;
     }
     
     
void enQueue(Queue *p,TreeNode *x){
    if(p->rear==N-1)
     queueMove(p);
     
     
     p->rear++;
     p->queuearray[p->rear]=*x;
     
     
     
     }
     
void deQueue(Queue *p,TreeNode *x){
 p->front++;
 *x=p->queuearray[p->front];
 
}

void queueMove(Queue *p){
     int i;
     for(i=p->front+1;i<=p->rear;i++)
     p->queuearray[i-p->front-1]=p->queuearray[i];
     p->rear=p->rear-p->front-1;
     p->front=-1;
     
     }

int isEmpty(Queue *p){
    if(p->rear==p->front)
    return 1;
    }


     
void levelOrder(TreeNode *ptr){
     TreeNode* k;
     
      createQueue(&q);
     
     enQueue(&q,ptr);
     while(!(isEmpty(&q))){
         
         deQueue(&q,k);
         ptr=k;         
         cout<<"Visit"<<k->value<<"  ";
         
         if(ptr->left!=NULL)
          enQueue(&q,ptr->left);
         if(ptr->right!=NULL)
          enQueue(&q,ptr->right); 
          
                 
                         } 
     
     }
     

void preorder(TreeNode *ptr){
     if(ptr!=NULL){
            cout<<ptr->value<<" ";     
            preorder(ptr->left);
            preorder(ptr->right);   
                 }
     } 
     
     
void inorder(TreeNode *ptr){
     if(ptr!=NULL){
            inorder(ptr->left);       
            cout<<ptr->value<<" ";
            inorder(ptr->right);
                   }
     }
     
void postorder(TreeNode *ptr){
     if(ptr!=NULL){
       postorder(ptr->left);
       postorder(ptr->right);
       cout<<ptr->value<<" ";
     
     }
     }
     
TreeNode* BST_delete(TreeNode *ptr,int x){
     
     int found=0,direction=0;
     TreeNode *r,*q,*s,*t;

     r=q=s=NULL;
     t=ptr;

    while(ptr!=NULL && !found)
    {
        if(x == ptr->value)
                found=1;
        else if(x< ptr->value)
        {
                direction=1;
                r=ptr;
                ptr=ptr->left;
        }
        else
        {
                direction=0;
                r=ptr;
                ptr=ptr->right;
        }
    }
    if(ptr == NULL)
        cout<<"找不到該節點"<<endl; 
        
        
    if(r == NULL)
    {
        if(ptr->right == NULL)
                return(ptr->left);
        else if(ptr->left == NULL)
                return(ptr->right);
    }
    if(ptr->right == NULL)
    {
        if(direction == 1)
                r->left=ptr->left;
        else
                r->right=ptr->left;
    }
    else if(ptr->left == NULL)
    {
        if(direction == 1)
                r->left=ptr->right;
        else
                r->right=ptr->right;
    }
    else
    {
        s=ptr;
        q=ptr->left;
        while(q->right != NULL)
        {
                s=q;
                q=q->right;
        }
        ptr->value=q->value;
        if(ptr == s)
                s->left=q->left;
        else
                s->right=q->left;
    }
     
     
     }