2cha shu.txt

二 叉 树 的 建 立 与 3 种 遍 利(前序,中序,后序三种),仅供参考之用

#include <stdlib.h>
#define MAX 20
#define NULL 0
typedef  int Status;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree；
Status CreateBiTree(BiTree *T)
{
  char ch;
  printf("\n输入二叉树的结点数据域内容:");
  ch=getchar();
  printf("%c",ch);
  if (ch=='#') (*T)=NULL;                    /* #代表空指针*/
  else {
    (*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点   */
    (*T)->data=ch;                        /*生成根结点  */
    CreateBiTree(&(*T)->lchild) ;         /*构造左子树  */
    CreateBiTree(&(*T)->rchild) ;         /*构造右子树  */
      }
  return ;
}
void PreOrder(BiTree T)
{
  if(T==NULL) return;
  printf("%2c",T->data);/*访问结点的数据域*/
/*前序遍历二叉树*/
  if(T->lchild!=NULL)
    PreOrder(T->lchild);  /*先序遍历左子树*/
  if(T->rchild!=NULL)
    PreOrder(T->rchild);  /*先序遍历右子树*/
}//PreOrder
void InOrder(BiTree T)
{
  if(T==NULL) return;
/*中序遍历二叉树*/
  if(T->lchild!=NULL)    
    InOrder(T->lchild);    /*中序遍历左子树*/
  printf("%2c",T->data);   /*访问结点的数据域*/
  if(T->rchild!=NULL)
    InOrder(T->rchild);    /*中序遍历右子树*/
}//InOrder
void PostOrder(BiTree T)
{
  if(T==NULL) return;
/*后序遍历二叉树*/
  if(T->lchild!=NULL)
    PostOrder(T->lchild);   /*后序遍历左子树*/
  if(T->rchild!=NULL)
    PostOrder(T->rchild);   /*后序遍历右子树*/
  printf("%2c",T->data);   /*访问结点的数据域*/
}//PostOrder
void LevleOrder(BiTree T)
{
/*层次遍历二叉树T*/
BiTree Queue[MAX],b;  /*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
  int front,rear;
   front=rear=0;
   if (T) /*若树非空*/
     {Queue[rear++]=T;           /*根结点入队列*/
      while (front!=rear)
      {       /*当队列非空*/
       b=Queue[front++];       　 /*队首元素出队列，并访问这个结点*/
       printf("%2c",b->data);
       if (b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空，则入队列*/ 
  if (b->rchild!=NULL) Queue[rear++]=b->rchild; /*右子树非空，则入队列*/
       }
     }
}//LevelOrder
int depth(BiTree T)
{  
/*求二叉树的深度*/
 int dep1,dep2;
 if (T==NULL) return 0;
  else {dep1=depth(T->lchild);
        dep2=depth(T->rchild);
        return dep1>dep2?dep1+1:dep2+1;
}
 }//depth
main()
{
  BiTree T=NULL;
  printf("\nCreate a Binary Tree\n");
  CreateBiTree(&T);  /*建立一棵二叉树T*/
  printf("\nThe preorder is:\n");
  PreOrder(T);       /*先序遍历二叉树*/
  printf("\nThe inorder is:\n");
  InOrder(T);       /*中序遍历二叉树*/
  printf("\nThe postorder is:\n");
  PostOrder(T);       /*后序遍历二叉树*/
  printf("\nThe level order is:\n");
  LevleOrder(T);     /*层次遍历二叉树*/
printf("\nThe depth is:%d\n",depth(T));     /*求二叉树的深度*/
}