#include<stdio.h>
#include<stdlib.h>
#define ELEMTP int

struct node
{
	ELEMTP data;
	struct node *lc,*rc;
};

struct node *root;
int m=0;

main()
{
	int cord;
	struct node* creat();
	void preorderz(struct node *t);
	void inorder(struct node *t);
	void postorder(struct node *t);
	void deletes(struct node *t,struct node *p,struct node *f);
	do
	{
		printf("\n         主菜單                   \n");
		printf("      1    建立二叉樹               \n");
		printf("      2    先序非遞歸遍歷           \n");
		printf("      3    中序遞歸遍歷             \n");
		printf("      4    后序遞歸遍歷，求葉節點數 \n");
		printf("      5    刪除節點                 \n");
		printf("      6    結束程序運行             \n");
		printf("---------------------------------------\n");
		printf("請輸入您的選擇(1, 2, 3, 4, 5, 6)");
		scanf("%d",&cord);
		switch(cord)
		{
			case 1:
				{
					root=creat();  // 建立二叉樹
					printf("建立二叉樹程序以執行完，\n");
					printf("請返回主菜單，用遍歷算法驗證程序的正確性  \n");
				}break;
			case 2:
				{
					preorderz(root);
				}break;
			case 3:
				{
					inorder(root);
				}break;
			case 4:
				{
					postorder(root);
				}break;
			case 5:
				{
					//deletes(root)
				}
			case 6:
				{
					printf("二叉樹程序執行完，再見！\n");
					exit(0);
				}
		}
	}while(cord<=6);
}

struct node* creat()
{
	struct node *t,*q,*s[30];
	int i,j,x;
	printf("i,x=");
	scanf("%d%d",&i,&x);//i是按滿二叉樹編號，x節點應有的序號，x是節點的數據
	while((i!=0)&&(x!=0))
	{
		q=(struct node*)malloc(sizeof(struct node));
		q->data=x;
		q->lc=NULL;	q->rc=NULL;
		s[i]=q;
		if(i==1)
			t=q;    //t代表樹根節點
		else
		{
			j=i/2; //雙親節點的編號
			if((i%2)==0)
				s[j]->lc=q;
			else
				s[j]->rc=q;
		}
		printf("i,x=");
		scanf("%d%d",&i,&x);
	}
	return(t);
}

/*void preorderz(struct node* p)//前序非遞歸算法
{
	struct node *q,*s[30]; //s輔助棧
	int top,bools;
	q=p;top=0;  //棧頂指針
	bools=1;  //bools=1為真值繼續循環；bools=0為假時棧空，結束循環
	do
	{
		while(q!=NULL)
		{
			printf("%6d",q->data);     //訪問節點
			top++;
			s[top]=q;
			q=q->lc;
		}
		if(top==0)
			bools=0;
		else
		{
			q=s[top];
			top--;
			q=q->rc;
		}
	}while(bools);
	printf("\n");
}//////////////////////////結束preorderz*/

void preorderz(struct node* p)//前序遞歸遍歷
{
	if(p!=NULL)
	{
		printf("%6d",p->data);
		inorder(p->lc);
		inorder(p->rc);
	}
}

void inorder(struct node* p)//中序非遞歸遍歷
{
	struct node *s[30],*q;
	int top,bools;
	q=p;top=0;
	bools=1;
	do
	{
		while(q!=NULL)
		{
			top++;
			s[top]=q;
			q=q->lc;
		}
		if(top==0)
			bools=0;
		else
		{
			q=s[top];
			top--;
			printf("%6d",q->data);
			q=q->rc;
		}	
	}while(bools);
}

/*void inorder(struct node* p)
{
	if(p!=NULL)
	{
		inorder(p->lc);
		printf("%6d",p->data);
		inorder(p->rc);
	}
}//////////////////////////結束inorder*/

void postorder(struct node* p)
{
	struct node *s[30],*s2[30],*q;
	int top,bools;
	q=p;top=0;
	bools=1;
	do
	{
		while(q!=NULL)
		{
			top++;
			s[top]=q;
			s2[top]=1;
			q=q->lc;
		}
		if(top==0)
			bools=0;
		else
		{
			if(s2[top]==1)
			{
					s2[top]=2;
					q=s[top];
					q=q->rc;
				}
			else
			{
				q=s[top];
				s2[top]=0;
				top--;
				printf("%6d",q->data);
				q=NULL;
			}
		}
	}while(bools);
}

void deletes(struct node *t,struct node *p,struct node *f)
{
	struct node *s,*q;
	int bools=1;
	if(p->lc==NULL)
		s=p->rc;
	else if(p->rc==NULL)
	{
		s=p->rc;
		while(s->lc!=NULL)
		{
			q=s;
			s=s->rc;
		}
		if(q==p)
			q->rc=s->rc;
		else
			q->lc=s->rc;
		p->data=s->data;
		free(s);
		bools=0;
	}
	if(bools==1)
	{
		if(f==NULL)
			t=s;
		else if(f->lc==p)
			f->lc=s;
		else
			f->rc=s;
		free(p);
	}
}

/*void postorder(struct node* p)
{
	if(p!=NULL)
	{
		postorder(p->lc);
		postorder(p->rc);
		printf("%6d",p->data);
		if(p->lc==NULL&&p->rc==NULL)
			m++;    //統計葉子節點
	}
}//////////////////////////結束postorder*/