[数据结构与算法]树与二叉树的基本数据结构类型，及其基本操作

#include<iostream>
using namespace std;
#define QueueSize 50
#define MaxSize 100
typedef char ElemType;
typedef struct BiNode{
	ElemType data;
	BiNode *lchild,*rchild;
}BiNode;
typedef struct element{
	BiNode *ptr;
	int flag;
}element;

void preorder(BiNode *root){//前序遍历的递归算法 
	if(root==NULL)return;
	else{
		cout<<root->data;
		preorder(root->lchild);
		preorder(root->rchild);
	}
}
void creat(BiNode *&root){//建立二叉递归算法 
	ElemType ch;
	cin>>ch;
	if(ch=='#')root=NULL;
	else{
		root=new BiNode;
		root->data=ch;
		creat(root->lchild);
		creat(root->rchild);
	}
}
void CreateBiTree1(BiNode *&boot,char *str)
{
	BiNode *s[MaxSize],*p=NULL;
	int top=-1,k,j=0;  
	char ch;
	boot=NULL;				//建立的二叉树初始时为空
	ch=str[j];
		while (ch!='\0')	//str未扫描完时循环
	{
   	   	switch(ch) 
		{
		case '(':top++;s[top]=p;k=1; break;		//为左结点
		case ')':top--;break;
		case ',':k=2; break;                      	//为右结点
		default:p=new BiNode;
			p->data=ch;p->lchild=p->rchild=NULL;
		         	if (boot==NULL)					//*p为二叉树的根结点
						boot=p;
					else  							//已建立二叉树根结点
					{	
						switch(k) 
						{
						case 1:s[top]->lchild=p;break;
						case 2:s[top]->rchild=p;break;
						}
					}
		}
		j++;
		ch=str[j];
	}
}
void DispBiTree(BiNode *root) {//广义表形式输出二叉树 
	if (root!=NULL)
	{
		cout<<root->data;
		if (root->lchild!=NULL || root->rchild!=NULL)
		{
			cout<<"(";
			DispBiTree(root->lchild);
			if (root->rchild!=NULL) cout<<",";
			DispBiTree(root->rchild);
			cout<<")";
		}
	}
}
void postorder(BiNode *root){//后序遍历的非递归算法 
	element s[20];
	int top=-1;
	BiNode *p=root;
	while(p!=NULL||top!=-1){
		while(p!=NULL){
			top++;
			s[top].ptr=p;
			s[top].flag=0;
			p=p->lchild;
		}
		if(top!=-1){
			if(s[top].flag==0){
				p=s[top].ptr;
				s[top].flag=1;
				p=p->rchild;
			} 
			else cout<<s[top--].ptr->data <<" "; 
		}
	}
}

int main(){
	BiNode *b;
	CreateBiTree1(b,"A(B(D(,G)),C(E,F))");
	cout<<"前序遍历 ";
	preorder(b);//前序遍历 
	cout<<endl;
	cout<<"广义形式 ";
	DispBiTree(b);//广义形式输出二叉树
	cout<<endl;
	cout<<"后序遍历 " ;
	postorder(b);//后序遍历
	cout<<endl;
	cout<<"层次输出二叉树";
	
}