//#include"TBTree.h"
#include<iostream.h>
#include<strstrea.h>
#include<string.h>
#include<stdlib.h>
#include<iomanip.h>
struct TreeNode1{

	char data;
	int ltag;
	int rtag;
	TreeNode1*left;
	TreeNode1*right;
	
};

class PreTree
{
public:
	TreeNode1 *BT;
	TreeNode1 *pre;
	PreTree();
	void CreatPreTree();
    void Print(TreeNode1*p);
	void ThreadPreTree(TreeNode1*p);
    void PrintPreTBTree(TreeNode1*p);
    TreeNode1* PreTBTreePre(TreeNode1*p);
    TreeNode1* PreTBTreeNext(TreeNode1*p);
	void Print1(TreeNode1*p);
};

PreTree::PreTree(){
	BT=NULL;
	pre=NULL;
}

void PreTree::CreatPreTree()
{
	TreeNode1* s[10];
	int top=-1;
    TreeNode1*p;
	int k;
	char a[50];
b:
	int i=0;
	cout<<"輸入以'@'字符為結束符的二叉樹廣義表表示:"<<endl;
	char shu;
	cin>>shu;
	while(shu!='@'){
		a[i++]=shu;
		cin>>shu;
	}
	if(a[0]=='('||a[0]==')'||a[0]==','||a[i-1]!=')'){
		cout<<"廣義表輸入有錯!請重新輸入......"<<endl<<endl;
			goto b;
	}
	for(int j=0;j<i-1;j++){
		if(a[j]==','&&a[j+1]==','){
		cout<<"廣義表輸入有錯!請重新輸入......"<<endl<<endl;
				goto b;}
	if(a[j]=='('&&a[j+1]=='('){
        cout<<"廣義表輸入有錯!請重新輸入......"<<endl<<endl;
		goto b;
	}
	if((a[j]!='('&&a[j]!=','&&a[j]!=')')&&(a[j+1]!='('&&a[j+1]!=','&&a[j+1]!=')')){
        cout<<"廣義表輸入有錯!請重新輸入......"<<endl<<endl;
		goto b;
		}
	}
	a[i++]='@';
	istrstream ins(a);
	char ch;
	ins>>ch;
	while(ch!='@')
	{
		switch(ch)
		{
		case'(':
			top++;s[top]=p;k=1;
			break;
		case')':
			top--;
			break;
		case',':
			k=2;
			break;
		default:
			p=new TreeNode1;
			p->ltag=0;
			p->rtag=0;
			p->data=ch;
			p->left=p->right=NULL;
			
			if(BT==NULL)BT=p;
			else
			{
				switch(k)
				{
				case 1:
					s[top]->left=p;
					break;
				case 2:
					s[top]->right=p;				
				}			
			}		
		}
		ins>>ch;	
	}
}

void PreTree::Print(TreeNode1*p){
	if(p!=NULL){
    cout<<p->data;
	if(p->left!=NULL||p->right!=NULL){
        cout<<'(';
		Print(p->left);
		if(p->right!=NULL)cout<<',';
	
		Print(p->right);
		cout<<')';
	}
	}
}

void PreTree::ThreadPreTree(TreeNode1*p){

	
    if(p!=NULL){
        
		if(pre!=NULL&&pre->rtag==1)pre->right=p;
		if(p->left==NULL){
			p->ltag=1;
			p->left=pre;
		}
		if(p->right==NULL){
		    p->rtag=1;
		}
		pre=p;
		if(p->ltag==0)ThreadPreTree(p->left);
		if(p->rtag==0)ThreadPreTree(p->right);
	}
}

void PreTree::PrintPreTBTree(TreeNode1*p)
{
	while(p!=NULL){
    cout<<p->data<<setw(5);
	p=PreTBTreeNext(p);

	}
}

TreeNode1*PreTree::PreTBTreeNext(TreeNode1*p){
	if(p->ltag==1)return p->right;
	else return p->left;
}

TreeNode1*PreTree::PreTBTreePre(TreeNode1*p){
	if(p->ltag==1)return p->left;
	else return NULL;
}

void PreTree::Print1(TreeNode1*p){
	TreeNode1*pq;
	
	while(p!=NULL){
        cout<<setw(8)<<p->data<<setw(8)<<p->ltag<<setw(8);
		if(p->ltag==1)
		{
			pq=PreTBTreePre(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(16);
		cout<<p->rtag<<setw(8);
        if(p->rtag==1)
		{
			pq=PreTBTreeNext(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(8);
		p=PreTBTreeNext(p);
		cout<<endl;

	}
	
	
}

void choice1(){
	system("cls");
	cout<<endl;
	cout<<"             --------------前序線索二叉樹的前序遍歷--------------"<<endl<<endl;
	char c1;
	do{ 
    PreTree HT=PreTree();
    HT.CreatPreTree();
	cout<<endl;
	cout<<"二叉樹初始狀態廣義表形式的輸出:";
    HT.Print(HT.BT);
	cout<<endl<<endl;
	HT.ThreadPreTree(HT.BT);
    cout<<"對建立的二叉線索樹進行前序遍歷,序列為:";
    HT.PrintPreTBTree(HT.BT);
	cout<<endl<<endl;
	cout<<"按前序遍歷序列顯示各結點的線索以及所指結點:"<<endl<<endl;
	cout<<setw(42)<<"結點  左線索  左指針  右線索  右指針"<<endl<<endl;
    HT.Print1(HT.BT);
	cout<<endl;
	cout<<"是否繼續(y/n)";
	cin>>c1;
	}while(c1=='y'||c1=='Y');
}