树的存储与遍历

#include
#include

#define N 10

typedef int datatype;

typedef struct _btnode_
{
 datatype no;
 struct _btnode_ *lchild, *rchild;
} bitree;

typedef struct
{
 bitree *data[N];
 int front, rear;
} sequeue;

sequeue *CreateEmptyQueue()
{
 sequeue *sq;

 sq = (sequeue *)malloc(sizeof(sequeue));
 sq->front = sq->rear = 0;

 return sq;
}

void EnQueue(sequeue *sq, bitree *r)
{
 sq->rear = (sq->rear + 1) % N;
 sq->data[sq->rear] = r;

 return;
}

bitree *DeQueue(sequeue *sq)
{
 sq->front = (sq->front + 1) % N;
 
 return sq->data[sq->front];
}

int EmptyQueue(sequeue *sq)
{
 return (sq->front == sq->rear);
}

bitree *CreateBitree(int i, int n)
{
 bitree *root;

 root = (bitree *)malloc(sizeof(bitree));
 root->no = i;

 if (2*i <= n)
 {
  root->lchild = CreateBitree(2*i, n);
 }
 else
 {
  root->lchild = NULL;
 }
 
 if ((2*i+1) <= n)
 {
  root->rchild = CreateBitree(2*i+1, n);
 }
 else
 {
  root->rchild = NULL;
 }

 return root;
}

void PreOrder(bitree *root)
{
 printf("%d ", root->no);
 if (root->lchild != NULL) PreOrder(root->lchild);
 if (root->rchild != NULL) PreOrder(root->rchild);

 return;
}

void InOrder(bitree *root)
{
 if (root->lchild != NULL) InOrder(root->lchild);
 printf("%d ", root->no);
 if (root->rchild != NULL) InOrder(root->rchild);

 return;
}

void PostOrder(bitree *root)
{
 if (root->lchild != NULL) PostOrder(root->lchild);
 if (root->rchild != NULL) PostOrder(root->rchild);
 printf("%d ", root->no);

 return;
}

void NoOrder(bitree *root)
{
 sequeue *sq;
 bitree *r;

 sq = CreateEmptyQueue();
 EnQueue(sq, root);
 while ( ! EmptyQueue(sq) )
 {
  r = DeQueue(sq);
  printf("%d ", r->no);
  if (r->lchild != NULL) EnQueue(sq, r->lchild);
  if (r->rchild != NULL) EnQueue(sq, r->rchild);
 }

 printf("\n");
}

int main()
{
 bitree *root;

 root = CreateBitree(1, 10);
 printf("PreOrder  : ");
 PreOrder(root);
 printf("\n");
 
 printf("InOrder   : ");
 InOrder(root);
 printf("\n");
 
 printf("PostOrder : ");
 PostOrder(root);
 printf("\n");

 printf("NoOrder   : ");
 NoOrder(root);

 return 0;
}