// BinarySearchTree.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
#include<iomanip>
using namespace std;
template <class F> class queue;
template <class F>
class node
{
    friend class queue<F> ;
    private:
        F data;
        node<F>  * next;
};

template <class F>
class queue
{
    public:
        queue(){front=rear=NULL;}
        ~queue();
        void enqueue(F a);
        bool dequeue(F& savedeq);
        bool empty();
    private:
        node<F> * front;
        node<F> * rear;
};

template<class F>
queue<F>::~queue()
{
    node<F>* p;
    for(int i=0;front;i++)
    {
        p=front;
        front=front->next;
        delete p;
    }
}

template<class F>
bool queue<F>::empty()
{
    return front==NULL;
}

template<class F>
void queue<F>::enqueue(F a)
{
    node<F> * p=new node<F>;
    p->data=a;
    p->next=NULL;
    if(front==NULL&&rear==NULL)
    {
        rear=front=p;
    }
    else
    {
        rear->next=p;
        rear=p;
        
    }
}

template<class F>
bool queue<F>::dequeue(F& savedeq)
{
    if(front==NULL&&rear==NULL)
        return 0;
    node<F> * p=front;
    front=front->next;
    savedeq=p->data;
    if(front==NULL)
        rear=NULL;
    delete p;
    return 1;
}

template<class T> class binarytree;
template<class T>
class binarytreenode
{
    friend class binarytree<T>;
    public:
        binarytreenode()
        {
            data=0;
            leftchild=rightchild=NULL;
        }
        binarytreenode(binarytreenode<T>* m,binarytreenode<T>* n)
        {
            data=0;
            leftchild=m;
            rightchild=n;
        }
        binarytreenode(binarytreenode<T>* m,binarytreenode<T>* n,T mem)
        {
            data=mem;
            leftchild=m;
            rightchild=n;
        }
    private:
        T data;
        binarytreenode<T>* leftchild;
        binarytreenode<T>* rightchild;
};

template<class T>
class binarytree
{
    private:
        binarytreenode<T>* root;
        void createtree(binarytreenode<T>*& p, T);
        void preorder(binarytreenode<T>*& p);
        void inorder(binarytreenode<T>*& p);
        void postorder(binarytreenode<T>*& p);
    public:
        binarytree(){root=NULL;}
        ~binarytree(){delete root;}
        void create();
        void doorder();
        void stepcreate();
        void steporder();
};

template<class T>
void binarytree<T>::create()
{	
	cout<<"輸入節點編號以-1結束：";
    T value;
    cin>>value; 
	root=new binarytreenode<T>;
	binarytreenode<T>* p=root;
	while (value != -1)
	{
		createtree(p,value);
		cin >> value;
	}
}

template<class T>
void binarytree<T>::createtree(binarytreenode<T>*& root, T value)
{	
	binarytreenode<T> *ptr = new binarytreenode<T>;
	ptr->data = value;
	if(!root)
		root = ptr;
	else 
		if( ptr->data < root ->data)
			createtree( root ->leftchild, value );
	else 
		createtree( root ->rightchild, value);
}

template<class T>
void binarytree<T>::preorder(binarytreenode<T>*& p)
{
    if(p)
    {
        cout<<p->data<<" ";
        preorder(p->leftchild);
        preorder(p->rightchild);
    }
}

template<class T>
void binarytree<T>::inorder(binarytreenode<T>*& p)
{
    if(p)
    {
        inorder(p->leftchild);
        cout<<p->data<<" ";
        inorder(p->rightchild);
    }
}

template<class T>
void binarytree<T>::postorder(binarytreenode<T>*& p)
{
    if(p)
    {
        postorder(p->leftchild);
        postorder(p->rightchild);
        cout<<p->data<<" ";
    }
}    

template<class T>
void binarytree<T>::doorder()
{
    binarytreenode<T>* p=root;
    int ch;
    cout<<"輸入你想要的遍歷方式：1.先序2.中序3.后序"<<endl;
    cin>>ch;
    if(ch==1)
        preorder(p);
    if(ch==2)
        inorder(p);
    if(ch==3)
        postorder(p);
    cout<<endl;

}

template<class T>
void binarytree<T>::stepcreate()
{
    binarytreenode<T>* p;
    int ch;
    T x;
    queue<binarytreenode<T>* >q;
    root=new binarytreenode<T>;
    q.enqueue(root);
    while(!q.empty())
    {
        q.dequeue(p); 
        cout<<"輸入該節點編號：";
        cin>>x;
        p->data=x;
        cout<<"該節點左孩子是否存在，1.存在0.不存在:";
        cin>>ch;
        if(ch==1)
        {
            p->leftchild=new binarytreenode<T>;
            q.enqueue(p->leftchild);
        }
        else
            p->leftchild=NULL;
        cout<<"該節點右孩子是否存在，1.存在0.不存在:";
        cin>>ch;
        if(ch==1)
        {
            p->rightchild=new binarytreenode<T>;
            q.enqueue(p->rightchild);
        }
        else
            p->rightchild=NULL;
     }
}

template<class T>
void binarytree<T>::steporder()
{
    queue<binarytreenode<T>* >q;
    binarytreenode<T>* p=root;
    q.enqueue(p);
    while(!q.empty())
    {
        q.dequeue(p);
        cout<<p->data<<" ";
        if(p->leftchild)
            q.enqueue(p->leftchild);
        if(p->rightchild)
            q.enqueue(p->rightchild);
    }
    cout<<endl;
}

void main()
{
    binarytree<int> tree;
    int x;
bg:    cout<<"選擇你想要的建樹方式：0.遞歸建樹1.層次建數:";
    cin>>x;
    if(x==0)
        tree.create();
    else
        if(x==1)
            tree.stepcreate();
        else
            goto bg;
    tree.doorder();
    cout<<"以下是層次遍歷:"<<endl;
    tree.steporder();
    char u;
    cin>>u;
}