树的生成与操作.cpp

数据结构 之树的生成与操作 算法

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
#include<conio.h>
int i=0,j=0;
int s=0,t=0;
char a[20][10];
char b[20][10];
char c[20][10];
typedef struct BiTNode{
	  char data;
	  struct BiTNode *lchild,*rchild;
	  int flag;
	  int j;
	 }BiTNode,*BiTree;

typedef struct Stack{
	 BiTNode *base;
	 BiTNode *top;
	 int stacksize;

		  }Stack;

void InitStack(Stack &S){
	 S.base=(BiTNode*)malloc(50* sizeof(BiTNode));
	 if(!S.base)exit(0);
	 S.top=S.base;
	 S.stacksize=50;
}
void Push(Stack &S,BiTree T){
   if(S.top-S.base>=S.stacksize){
	S.base=(BiTNode *)realloc(S.base,(S.stacksize+10)*sizeof(BiTNode));
	if(!S.base)exit(0);
	S.top=S.base+S.stacksize;
	S.stacksize+=10;  }
	*S.top=(*T);
	S.top++;

}

void Pop(Stack &S,BiTree &e)
{
 if(S.top==S.base) return ;
 S.top--; (*e)=(*S.top);

 return ;
}

void CreateBiTree(BiTree &T)
{char ch;
 scanf("%c",&ch);
 if(ch==' ')
  {T=NULL;}
 else
 {if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(0);
  T->data =ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
 }
 return ;
}

void pre_order_digui(BiTree &BT,int flag)
{
if(BT!=NULL)
 {a[i][j]=BT->data;
  i++;j++;
  pre_order_digui(BT->lchild,0);
  pre_order_digui(BT->rchild,1);
 }
if(flag==1){j--;}
}

void pre_order_feidigui(BiTree T)
{i=j=0;
 Stack S;
 InitStack(S);
 BiTree p =T;
do{
  while(p!=NULL)
   {
   b[i][j]=p->data;
   i++;j++;
   if(p->rchild!=NULL&&p->lchild!=NULL)
	{p->j=j;p->flag=1;
	}
   else{p->j=0;p->flag=0;}
	Push(S,p);
	p=p->lchild;

   }
   if(S.top!=S.base)
	{
	Pop(S,p);
   if(p->flag==1&&p->rchild!=NULL)
	{j=p->j;
	}
   p=p->rchild;

	}
  }while(p!=NULL||S.top!=S.base);
}

void exchange_tree(BiTree &T,int flag)
{
 if(T!=NULL)
   {BiTNode *temp;
	temp=T->lchild;
	T->lchild=T->rchild;
	T->rchild=temp;
	c[s][t]=T->data;
	s++;t++;
	exchange_tree(T->lchild,0);
	exchange_tree(T->rchild,1);
   }
  if(flag==1){t--;}
}
void print(char s[20][10])
{
  for(int p=0;p<20;p++)
  { for(int q=0;q<10;q++)
	{printf("%c ",s[p][q]);
	}
	printf("\n");
   }
}

void main()
{
   BiTree bitree;
 for(int l1=0;l1<20;l1++)
   for(int m1=0;m1<10;m1++)
   {a[l1][m1]='* '; }
 for(int l2=0;l2<20;l2++)
   for(int m2=0;m2<10;m2++)
   {b[l2][m2]='* '; }
 for(int l3=0;l3<20;l3++)
   for(int m3=0;m3<10;m3++)
   {c[l3][m3]='* '; }
   printf("Please enter the tree member correctly to create a tree:\n");
   CreateBiTree(bitree);

   printf("the result of pre_order_digui:\n");
   pre_order_digui(bitree,0);
   print(a);
   printf("\n");
   getch();
   clrscr();

   printf("the result of pre_order_feidigui:\n");
   pre_order_feidigui(bitree);
   print(b);
   getch();
   printf("\n");
   clrscr();

   printf("the result of the exchanged tree:\n");
   exchange_tree(bitree,0);
   print(c);
   getch();
   clrscr();
}