9.cpp

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

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

typedef struct sq
{bitree elem;
 int front,rear;
}sq;
sq *initqueue()
{sq *q;
 q=(sq*)malloc(sizeof(sq));
 q->elem=(bitree)malloc(k*sizeof(struct node));
 if(!q->elem)return 0;
 q->front=q->rear=0;
 return q;
}

bitree dequeue(sq *q)
{bitree p;
 p=&(q->elem[q->front]);
 (q->front)++;
 return p;
}

void enqueue(sq *q,bitree t)
{q->elem[q->rear]=*t;
 (q->rear)++;
}

void travl(bitree t)
{sq *q;
 bitree p;
 q=initqueue();
 enqueue(q,t);
 while(q->front!=q->rear)
 {p=dequeue(q);
  printf("%c",p->data);
  if(p->lchild)enqueue(q,p->lchild);
  if(p->rchild)enqueue(q,p->rchild);
 }
}

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;          //建立根节点
	 printf("%c",t->data);
	 setup(t->lchild);//建立左子树
	 setup(t->rchild);//建立右子树
 }
 return 1;
}

void main()
{bitree t=null;
 printf("输入数值:");
 setup(t);
 printf("\n层次遍历:\n");
 travl(t);
 printf("\n");
}