/**********************************************************************二叉树的基本操作(1)二叉树的数据结构(2)二叉树的构造(3)二叉树遍历 ：先序，中序，后序************************************************************************/#include <cstdio>#include <cstdlib>const int MAX=20;//二叉树的结构 利用双链表实现typedef struct Node{	char ch;				 // 数据域	struct Node *plchild;    //左子树指针	struct Node *prchild;	//右子树指针}BiTreeNode;//构造二叉树 //1.按照先序遍历法构造 利用递归构造// ABD#G##EH##I##CF#J###void CreateBiTree_PreOrder(BiTreeNode * &T) //注意这里传入的是指针的引用{		char ch;	scanf("%c",&ch);	if(‘#‘==ch)		T=NULL;	else {		T=new BiTreeNode;		if(NULL==T)			exit(-1);		T->ch=ch;		CreateBiTree_PreOrder(T->plchild); // 构造左子树		CreateBiTree_PreOrder(T->prchild); // 构造右子树	}}//2.按照带括号的字符串创建二叉树结构/*思路：a(b(c,d),e(f(,g),h(i)))	‘(‘: 表明已创建的节点为双亲节点，入栈。将要创建左孩子节点，用flag=1标记	‘,‘: 表明将要创建右孩子节点。用flag=2标记	‘)‘: 表明左右孩子节点创建和链接完毕，父节点出栈。	default: 创建节点，并且赋值，判断链接情况 */void CreateBiTree_ByString(BiTreeNode* &T, char str[]){	BiTreeNode* Stack[MAX];		// 栈用于存储父节点	int top=0,flag=0;	BiTreeNode* p=NULL;			//用于临时指针	while(*str)	{		switch(*str)		{			case ‘(‘:					Stack[top++]=p;					flag=1;		//表示即将要创建的是 左孩子节点					break;			case ‘,‘:					flag=2;  //表明将要创建	右孩子节点					break;			case ‘)‘:					--top;	//将父节点出栈					break;			default:				{						p=new BiTreeNode;					if(NULL==p)						return  ;					if(T==NULL)						T=p;					p->ch=*str;					p->plchild=NULL;					p->prchild=NULL;					switch(flag) //此时 flag要初始化 不然非法访问					{						case 1:							Stack[top-1]->plchild=p; //将父节点与左孩子节点链接							break;						case 2:							Stack[top-1]->prchild=p; //将父节点与右孩子节点链接							break;					}					break;				}		}		++str;	}}// 递归先序遍历void PreOrderTraverse_Recur(BiTreeNode *T){		if(T) 	{		printf("%2c",T->ch);		PreOrderTraverse_Recur(T->plchild);		PreOrderTraverse_Recur(T->prchild);	}}// 非递归先序遍历/* 思路: 先访问父节点，打印。然后压入栈中，然后访问左孩子节点，访问打印压栈。		将左孩子一个个压入栈中，直到NULL.然后在访问右孩子节点。同理按前 */void PreOrderTraverse_NoRecur(BiTreeNode *T){	BiTreeNode* Stack[MAX]; //利用数组构造栈 先进后出	int top=0;	BiTreeNode *p=T;	while( p || top >0)	{		while(p)		{			printf("%2c",p->ch);	//先访问			Stack[top++]=p;		//将 父节点压栈			p=p->plchild;		//访问左孩子节点		}		if(top>0)	//top 代表栈中有多个节点		{ //开始访问 右孩子节点			p=Stack[--top];		//如果某个父节点的左孩子节点为NULL 那么出栈该父节点。			p=p->prchild;		//然后又跳入到 访问该右孩子的左子树		}	}}// 递归中序遍历void InOrderTraverse_Recur(BiTreeNode *T){	if(T)  //如果节点不为NULL 	{			InOrderTraverse_Recur(T->plchild); //先放问 左孩子树		printf("%2c",T->ch);		   //然后在 访问根节点		InOrderTraverse_Recur(T->prchild); // 然后在访问 右孩子树	}}// 非递归中序遍历 /* 思路：相比于先序而言(一直将父节点压栈，父节点出栈的时候就是要访问该节点的右孩子树）		 所以中序遍历，一直压入左孩子节点,直到NULL.在出栈的时候打印父节点值。 */void InorderTraverse_NoRecur(BiTreeNode *T){	BiTreeNode* Stack[MAX];	int top=0;	BiTreeNode *p=T;	while( p || top>0 )	{		while(p)		{			Stack[top++]=p;  //直接将父节点入栈			p=p->plchild;	// 然后访问左子树		}		if(top>0)		{			p=Stack[--top];		 //将父节点处栈			printf("%2c",p->ch); //打印父节点值			p=p->prchild;		 //访问右孩子子树		}	}}// 递归后序遍历void AfterOrderTraverse_Recur(BiTreeNode *T){	if(T)	{		AfterOrderTraverse_Recur(T->plchild);		AfterOrderTraverse_Recur(T->prchild);		printf("%2c",T->ch);		}}// 非递归后序遍历/*思路：依旧是将父节点依次压栈。直到左节点为NULL,此时不出栈父节点，而是直接访问右孩子节点		同时设定q用于检测是否已经访问过右孩子节点。 */void AfterOrderTraverse_NoRecur(BiTreeNode *T){	BiTreeNode* Stack[MAX];	int top=0;	BiTreeNode *p=T,*q=NULL; // q用于判断右节点是否访问过	while(p || top>0)	{		while(p) //直到没有左孩子节点		{			Stack[top++]=p;			p=p->plchild; 		}		if(top>0)		{			p=Stack[top-1]; //不出栈 直接访问右子树			if(p->prchild==NULL || p->prchild == q) //没有右节点或者右节点已经访问过			{				printf("%2c",p->ch);				q=p;				p=NULL;				top--;			}			else //有右节点 且没被访问过				p=p->prchild;		}	}	}//销毁二叉树void DestoryBiTree(BiTreeNode* &T){	if(T)	{		if(T->plchild)			DestoryBiTree(T->plchild);		if(T->prchild)			DestoryBiTree(T->prchild);		delete T;		T=NULL;	}}int main(){//ABD#G##EH##I##CF#J###	BiTreeNode *T=NULL;	CreateBiTree_PreOrder(T);	puts("递归先序遍历:");	PreOrderTraverse_Recur(T);	puts("");	puts("非递归先序遍历:");	PreOrderTraverse_NoRecur(T);	puts("");	puts("递归中序遍历:");	InOrderTraverse_Recur(T);	puts("");	puts("非递归中序遍历:");	InorderTraverse_NoRecur(T);	puts("");	puts("递归后序遍历:");	AfterOrderTraverse_Recur(T);	puts("");	puts("非递归后序遍历:");	AfterOrderTraverse_NoRecur(T);	puts("");	DestoryBiTree(T);	//销毁二叉树	puts("\n--按照带括号的字符串输入------------");	BiTreeNode *T2=NULL;	char str[]="a(b(c,d),e(f(,g),h(i)))";	CreateBiTree_ByString(T2,str);	puts("递归先序遍历:");	PreOrderTraverse_Recur(T2);	puts("");	puts("非递归先序遍历:");	PreOrderTraverse_NoRecur(T2);	puts("");	puts("递归中序遍历:");	InOrderTraverse_Recur(T2);	puts("");	puts("非递归中序遍历:");	InorderTraverse_NoRecur(T2);	puts("");	puts("递归后序遍历:");	AfterOrderTraverse_Recur(T2);	puts("");	puts("非递归后序遍历:");	AfterOrderTraverse_NoRecur(T2);	puts("");	//DestoryBiTree(T2);	//销毁二叉树}