9.1.cpp

约瑟夫环源代码,前中后序递归遍历二叉树

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define null 0
#define max 100
typedef struct node
{ char data;
  struct node *lchild;
  struct node *rchild;
}tree,* bitree;

int i,j;

int setup(bitree &t)
{char ch=' ';
 scanf("%c",&ch);
 if(ch==' ')t=null;
 else{
	 if(!(t=(node *)malloc(sizeof(node))))return 0;
	 t->data=ch;          //建立根节点
	 setup(t->lchild);//建立左子树
	 setup(t->rchild);//建立右子树
 }
 return 1;
}


int travl(bitree t)//后序遍历的递归调用
{if(t)
{ if(t->lchild!=null){i=i+1;travl(t->lchild);}//访问左子树
  if(t->rchild!=null){i=i+1;travl(t->rchild);}//访问右子树
  if(i>j)j=i;
  i=i-1;
  return 1;
 }
else return 0;
}

int travl1(bitree t)
{//printf("输入数值:");
 int m=0,n=0,a,b,k=1;
 i=0;
 tree *p[max][max];
 p[m][n]=t;
 printf("%c",p[m][n]->data);
 for(a=1;a<=j+1;a++){
	 k=k*2;
	 for(b=0;b<k;b++){
		 if(p[m][n]){
			 p[a][b]=p[m][n]->lchild;
		     if(p[a][b])printf("%c",p[a][b]->data);
		     b++;
		     p[a][b]=p[m][n]->rchild;
		     if(p[a][b])printf("%c",p[a][b]->data);
		 }
		 else {b++;}
		 n++;
	 }
	 m++;
	 n=0;
}printf("输入数值:");
 return 1;
}

void main()
{bitree t=null;
 i=0;j=0;
 int deep;
 printf("输入数值:");
 setup(t);
 travl(t);
 deep=j+1;
 printf("deep=%d\n",deep);
 travl1(t);
 printf("\n结束");
}
//ab c  de  f  
//abc  de g  f   
//ab d  ce