bltree.c

c语言一些基础编码

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"

#include <stdio.h>
#include <conio.h>

#include <stdlib.h>
#include <malloc.h>



#define MaxSize     100
#define M  100
#define Null  0

typedef struct trnode
 {
  int data;
  struct trnode *lchild,*rchild;
 } BITREE;

BITREE *que[MaxSize];

int front=0,rear=0;

BITREE *creat() /* 建立二叉树 */
/* 按先序遍历方式输入，每个叶子节点后补0表示结束 */
{
 BITREE *tr;
 int x;
 printf("\nInput the value of the tree node:\n");
 scanf("%d",&x);
 if(x==0) tr=Null;
 else
 {
  tr=(BITREE *)malloc(sizeof(BITREE));
  tr->data=x;
  tr->lchild=creat();
  tr->rchild=creat();
 }
 return (tr);
}
 /* creat */

void InOrder(BITREE *t) /* 中序遍历二叉树 */
{
 if(t!=Null)
 {
   InOrder(t->lchild);
   printf("%4d",t->data);
   InOrder(t->rchild);
 }
} /* end of inorder */

void EnQueue(BITREE *t)
{
 if(front!=(rear+1)%M)
 {
  rear=(rear+1)%M;
  que[rear]=t;
 }
}/* Enqueue */

BITREE *DeQueue()
{
 if(front==rear) return Null;
 front=(front+1)%M;
 return (que[front]);
}/* Delqueue */

void levorder(BITREE *t)
{
 BITREE *p;
 if(t!=Null)
 {
  EnQueue(t);
  while(front!=rear)
  {
   p=DeQueue();
   printf("%4d",p->data);
   if(p->lchild!=Null)
     EnQueue(p->lchild);
   if(p->rchild!=Null)
     EnQueue(p->rchild);
  }
 }
}/* LevOrder */


int main()
{
 BITREE *root;
 printf("\n");
 root=creat();
 printf("\n中序遍历结果：\n");
 InOrder(root);
 printf("\n");
 printf("\n按层次遍历的结果：\n");
 levorder(root);
 getch();
} /* main */

void levorder2(BITREE *t)
/* 采用非递归方式实现的按层次遍历二叉树*/
{
 BITREE *Que[MaxSize];
 /* 队列Que 为一个指向BITREE 类型变量的指针数组 */
 int front,rear;
 if(t!=Null)
 {
  front=0;
  rear=1;
  Que[1]=t;
  do
  {
   front=(front+1)%MaxSize;
   t=Que[front];
   printf("%d",t->data);
   if(t->lchild!=Null)
   {
    rear=(rear+1)%MaxSize;
    Que[rear]=t->lchild;
   }
   if(t->rchild!=Null)
   {
    rear=(rear+1)%MaxSize;
    Que[rear]=t->rchild;
   }

  }while(rear==front);
 }
} /* levorder */