ex9-1.cpp

遍历二叉树并使用3种方法统计结点与叶子结点

#include <stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef char Status;
typedef char ElemType;
typedef struct BiTNode
{  ElemType data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {
  char ch;
  ch=getchar();
  if (ch==' ') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    T->data = ch;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
  }
  return OK;
}

void PreDisplayBiTree(BiTree T)
{  if(T)
   {  printf("%c ",T->data);
      PreDisplayBiTree(T->lchild);
      PreDisplayBiTree(T->rchild);
   }
}

void InDisplayBiTree(BiTree T)
{  if(T)
   {  InDisplayBiTree(T->lchild);
      printf("%c ",T->data);
      InDisplayBiTree(T->rchild);
   }
}

void PostDisplayBiTree(BiTree T)
{  if(T)
   {  PostDisplayBiTree(T->lchild);
      PostDisplayBiTree(T->rchild);
      printf("%c ",T->data);
   }
}

int CountNode;
void PreCountNode(BiTree T)
{  if (T)
   {  CountNode++;
      PreCountNode(T->lchild);
      PreCountNode(T->rchild);
   }
}



int InCountNode(BiTree T)
{  static int NodeSum;
   if (T)
   { InCountNode(T->lchild);
     NodeSum++;
     InCountNode(T->rchild);
     }
   return(NodeSum);
}


int PostCountNode(BiTree T,int &NodeSum)
{  if (T)
   {   PostCountNode(T->lchild,NodeSum);
       PostCountNode(T->rchild,NodeSum);
       NodeSum++;
       }
   return OK;
}

int CountLeaf;
void PreCountLeaf(BiTree T)
{  if (T)
   {  if(T->lchild==NULL&&T->rchild==NULL)
        CountLeaf++;
      PreCountLeaf(T->lchild);
      PreCountLeaf(T->rchild);
   }
}


int InCountLeaf(BiTree T)
{  static int LeafSum;
   if (T)
   {  
      InCountLeaf(T->lchild);
      if(T->lchild==NULL&&T->rchild==NULL)
         LeafSum++;
      InCountLeaf(T->rchild);
    }
   return LeafSum;
}


int PostCountLeaf(BiTree T,int &LeafSum)
{  if (T)
   {  
      PostCountLeaf(T->lchild,LeafSum);
      PostCountLeaf(T->rchild,LeafSum);
      if(T->lchild==NULL&&T->rchild==NULL)
         LeafSum++;
   }
   return OK;
}
void main()
{
   BiTree T;
   int i,j=0,m,n=0;
   CreateBiTree(T);
   PreDisplayBiTree(T);
   printf("\n");
   InDisplayBiTree(T);
   printf("\n");
   PostDisplayBiTree(T);
   printf("\n");
   printf("The number of the Nodes(Pre):");
   PreCountNode(T);
   printf("%d ",CountNode);
   printf("\n");
   printf("The number of the Nodes(In):");
   i=InCountNode(T);
   printf("%d ",i);
   printf("\n");
   printf("The number of the Nodes(Post):");
   PostCountNode(T,j);
   printf("%d ",j);
   printf("\n");
   printf("The number of the Leaves(Pre):");
   PreCountLeaf(T);
   printf("%d ",CountLeaf);
   printf("\n");
   printf("The number of the Leaves(In):");
   m=InCountLeaf(T);
   printf("%d ",m);
   printf("\n");
   printf("The number of the Leaves(Post):");
   PostCountLeaf(T,n);
   printf("%d ",n);
   printf("\n");
}