expe2.cpp

一些数据结构的源码

#include<iostream>
using namespace std;
#define elemtype char
#define NULL 0
void (* p)(elemtype);
typedef struct bitnode
{
	elemtype data;
	struct bitnode * lchild,* rchild;
}bitnode,* bitree;

#include "level.cpp"
#define stack_init_size 30
#define stackincrement 10
typedef struct 
{
	bitree *base,*top;
	int stacksize;
}sqstack;

void stackinit(sqstack & S)
{
   S.base=(bitree*)malloc(stack_init_size*
   sizeof(bitree));
   S.top=S.base;
   S.stacksize=stack_init_size;
}

void push(sqstack &S,bitree &e)
{
	if(S.top-S.base==S.stacksize)
	{
	    S.base=(bitree*)realloc(S.base,
        (S.stacksize+stackincrement)*
        sizeof(bitree));
		S.top=S.base+S.stacksize;
		S.stacksize+=stackincrement; 
	}//if
	*S.top=e;S.top+=1;
}//push

int stackempty(const sqstack &S)
{
	if(S.top==S.base) return 1;
	else return 0;
}

int pop(sqstack &S,bitree &e)
{
   if(!stackempty(S)) {S.top-=1;e=*S.top;return 1;}
   else return 0;
}

int gettop(sqstack S,bitree &p)
{
   if(!stackempty(S)) p=*(S.top-1);return 1;
}

void visit(elemtype e)
{
	cout<<e;
}

void dcreatebitree(bitree &T)
{
	char ch;cin>>ch;
    if(ch=='o') T=NULL;
    else
	 {
		T=(bitree)malloc(sizeof(bitnode));
	    T->data=ch;dcreatebitree(T->lchild);
		dcreatebitree(T->rchild); 
	}  
}


int fdcreatebitree(bitree &T)
{
	elemtype ch;bitree p;sqstack S;
    stackinit(S);cin>>ch;
    if(ch=='o') 
	{
		T=NULL;return 1;
	}
    T=(bitree)malloc(sizeof(bitnode));
    T->data=ch;p=T;cin>>ch;
    do
	{
		while(ch!='o')
		{
         p->lchild=(bitree)malloc(sizeof
(bitnode));
	  push(S,p);p=p->lchild;
 	  p->data=ch;cin>>ch;
		}
    p->lchild=NULL;
//向左走到底
//右走一步
    cin>>ch;
   while(ch=='o'&&!stackempty(S))
   {
	p->rchild=NULL;pop(S,p);cin>>ch;
   }
    if(ch=='o') p=p->rchild=NULL;
   else 
   {
	   p->rchild=(bitree)malloc(sizeof(bitnode));
      p=p->rchild;p->data=ch;cin>>ch;
   }
	}while(p);//do_while
return 1;
}//createbitree

void Preordertraverse(bitree T,void (* visit)(elemtype e))
{  
	if(T)
	{
		visit(T->data);
		Preordertraverse(T->lchild,p);
		Preordertraverse(T->rchild,p);
	}  
}
void Inordertraverse(bitree T,void (* visit)(elemtype e))
{   
	if(T)
	{
		Inordertraverse(T->lchild,p);
		visit(T->data);
		Inordertraverse(T->rchild,p);
	}  
}
void Lordertraverse(bitree T,void (* visit)(elemtype e)) 
{ 
	if(T)
	{
		Lordertraverse(T->lchild,p);
        Lordertraverse(T->rchild,p);
		visit(T->data);
	}  
}

void main()
{
	p=visit;  bitree T;
    int i;
    cout<<"请选择要进行的操作：0为递归建立二叉树，1为非递归建立二叉树"<<endl;
    cin>>i;
    if(i==0)
	{
	  cout<<"请输入数据："<<endl;
      dcreatebitree(T);
	}
    else if(i==1)
	{
	  cout<<"请输入数据："<<endl;
      fdcreatebitree(T);
	}
	int j;
		while(1)
	{
    	cout<<"请选择要遍历的类型：1为先序，2为中序，3为后序，4为层次，0为退出"<<endl;
		cin>>j;
		if(j==1)
		{
           cout<<endl<<"先序序列:"<<endl;
           Preordertraverse(T,p);
		   cout<<endl;
		}
		else if(j==2)
		{
            cout<<endl<<"中序序列:"<<endl;
            Inordertraverse(T,p);
			cout<<endl;
		}
		else if(j==3)
		{
            cout<<endl<<"后序序列:"<<endl;
            Lordertraverse(T,p);
			cout<<endl;
		}
		else if(j==4)
		{
           cout<<endl<<"层次遍历序列为:"<<endl;
           leordertraverse(T,p);
		   cout<<endl;
		}
		else if(j==0)break;
	}
    cout<<endl;
}