先中序列生成树.cpp

海明码 出站入站序列 非递归生成树 九格填质数 七子控棋盘等等算法

#include<stdio.h>
#include<malloc.h>
typedef struct bitree{
struct bitree *rig,*lef;
char data;
int flag;
char p;
}*tree,treenote;
treenote btrees;

char *ch;
char *prestr;
void creat(tree& btree,char censtr[])
{
int i;
char soncen[20];
   if((*prestr)!='\0' && censtr[0]!='\0'){

    int flag=1;
			   int k;
     for(i=0;censtr[i]!='\0';i++) if
				(censtr[i]==*prestr)
		  { flag=0;break;}
		if(!flag)
		   {    btree->data=*prestr++;

		     for(k=0;k<i;k++) soncen[k]=censtr[k];
		     soncen[k]='\0';

		     btree->lef=(tree)malloc(sizeof(treenote));
		     btree->rig=(tree)malloc(sizeof(treenote));
			creat(btree->lef,soncen);
			creat(btree->rig,censtr+i+1);
			}
		 else {btree->lef=NULL;btree->rig=NULL;}

 }
 else {btree->data='#';btree=NULL;}
 }
 void preorder(tree btrees)
{
  if (btrees)
	{        printf("%c",btrees->data);
		 preorder(btrees->lef);
		 preorder(btrees->rig);

	}
   else printf("%c",'*');
 }
    void main()
{char censtr[20];
 char pre[20];
 tree tr[40],tp;
 int base,top;
 printf("enter the preorder:\n");
 gets(pre);
 prestr=pre; //this is necessary;a pointer must be assigmented;
 printf("enter the centralorder:\n");
 gets(censtr);
 creat(&btrees,censtr);
preorder(&btrees);
/*printf("\n");
		base=top=-1;
		tr[++top]=&btrees; tp=&btrees; tp->flag=1;
    while (base!=top){
	 while(tp->lef && !tp->lef->flag)
	 {tp=tp->lef;tp->flag=1;tr[++top]=tp;}
	 if (tp->rig && !tp->rig->flag)
	 {tp=tp->rig;tp->flag=1;tr[++top]=tp;}
    else
    {
      printf("%c",tp->data);
      top--;
      tp=tr[top];
     }
		}
		printf("\n");
  */
}