c实现二叉树.txt

数据结构课程设计内容：模拟二叉排序树

#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>

#define max 30
#define queuesize 100



typedef char datatype;

typedef struct node{      /*定义二叉树链表结点结构*/

  datatype data;

struct node *lchild,*rchild;

}BinTNode,*BinTree;

typedef struct
{
  int front,rear;

  BinTree data[queuesize];  /*定义循环队列元素类型为二叉链表指针*/

  int count;

}cirqueue;       /*定义循环队列结构*/


void CreateBinTree(BinTree *T)  /*先序递归建立二叉树*/

    {

     char ch;

     scanf("\n%c",&ch);

     if (ch=='0')  *T=NULL;            /*读入0时，将相应结点置空*/

     else {*T=(BinTNode*)malloc(sizeof(BinTNode));  /*生成结点空间*/

            (*T)->data=ch;

            CreateBinTree(&(*T)->lchild);     /*构造二叉树的左子树*/

            CreateBinTree(&(*T)->rchild);     /*构造二叉树的右子树*/

           }

}



void PreOrder(BinTree t)        /*递归先序遍历*/
{
  if(t==NULL) return;

  printf("%c",t->data);

  PreOrder(t->lchild);

  PreOrder(t->rchild);
}

void InOrder(BinTree t)        /*递归中序遍历*/
{
  if(t==NULL) return;

  InOrder(t->lchild);

  printf("%c",t->data);

  InOrder(t->rchild);
}

void PostOrder(BinTree t)      /*递归后序遍历*/
{
  if(t=NULL) return;

  PostOrder(t->lchild);

  PostOrder(t->rchild);

  printf("%c",t->data);
}


void LevelOrder(BinTree t)   /*层次遍历*/
{ cirqueue *q;

  BinTree p;

  q=(cirqueue *)malloc(sizeof(cirqueue)); /*申请循环队列空间*/
  if(!q) return;

  q->count=q->rear=q->front=0; /*将循环队列初始化为空*/

  q->data[q->rear]=t;       /*把根结点入队列*/
  q->count++;
  q->rear=(q->rear+1)%queuesize;  /*判断队列是否为真溢出*/

  while(q->count)

    { if(q->data[q->front])  /*如果首元素不为空*/
        { p=q->data[q->front];
          printf("%c",p->data);   /*打印根结点元素*/

          q->front=(q->front+1)%queuesize;
          q->count--;        /*队首元素出列*/

          if(q->count==queuesize)   /*判断是否队满*/
            return;
          else
            { q->data[q->rear]=p->lchild;   /*左孩子入列*/
              q->count++;
              q->rear=(q->rear+1)%queuesize;
            }

          if(q->count==queuesize)
            return;
          else
            { q->data[q->rear]=p->rchild;      /*右孩子入列*/
              q->count++;
              q->rear=(q->rear+1)%queuesize;
            }
          }

      else   /*如果队首为空指针，将空指针出列*/
        { q->front=(q->front+1)%queuesize;
          q->count--;
        }
    }
}

main()
{ BinTree bt;

  CreateBinTree(&bt);

  LevelOrder(bt);

  getch();
}