#include"stdlib.h"    /* 存储分配头文件，或用"malloc.h" */
#include"stdio.h"     /* 标准I/O头文件 */
#include"ctype.h"  
#define N 10000                     /* 定义NULL,本行可省去 */
#define LENG sizeof(struct Bnode)  /* 确定结点所占空间的字节数 */
typedef char ElemType;            /* 抽象元素类型为char类型 */


typedef struct Bnode              /* Bnode为结点(C结构体)类型 */
{ ElemType data;                 /* data为抽象元素类型 */
   struct Bnode *lchild, *rchild; /* 为指针类型  */
   signed size;
}Bnode;
int node[4] ;
int creat_tree(Bnode**root )   /* root是指向指针的指针类型 */
{ /* 本算法递归生成二叉树 */
      ElemType ch;
      scanf("%c",&ch);                                       /* 输入结点,字符型 */
      if (ch==' '){ (*root)->data=NULL;
                            return;}                       /* 生成空二叉树 */
      else                                                              /* 生成非空二叉树 */
       { (*root)=(Bnode*)malloc(LENG);       /* 申请结点空间 */
     (*root)->data=ch;                       /* 生成根结点 */
     creat_tree(&(*root)->lchild); /* 递归生成左子树 */
     creat_tree(&(*root)->rchild);    /* 递归生成右子树 */
        }
} /* creat_tree */

void preorder1(Bnode *root)
{                                                    /* 前序遍历二叉树 */
   if (root)
  {    printf("%c",root->data);
     if(root->lchild)preorder1(root->lchild);
     if(root->rchild)preorder1(root->rchild);
  }
} /* preorder */

void preorder2(Bnode *root)
{                                                    /* 中序遍历二叉树 */
    if (root)
    {
         if(root->lchild)preorder2(root->lchild);
         printf("%c",root->data);
        if(root->rchild)preorder2(root->rchild);
     }
} /* preorder */

void preorder3(Bnode *root)
{                                                    /* 后序遍历二叉树 */
        if (root)
       {
            if(root->lchild)preorder3(root->lchild);
            if(root->rchild)preorder3(root->rchild);
            printf("%c",root->data);
       }
} /* preorder */

void preorder4(Bnode *root)/*中序非递归遍历二叉树*/
{   Bnode  *p,*stack[N];
     int top=0;
      p=root;
do{
    while(p!=NULL)
    {
      top++;
      stack[top]=p;
      p=p->lchild;
    }
    if(top>0)
   {
     p=stack[top];/*p所指的 节点为无左子树或其左子树已经遍历过*/
      top--;
     printf("%c",p->data);
     p=p->rchild;
   }
}while(p!=NULL||top!=0);
} /* preorder */

void preorder5(Bnode *root)/*先序非递归遍历二叉树*/
{   Bnode  *p,*stack[N];
     int top ;
      p=root;
   if(root!=NULL)
        {top=1;
          stack[top]=p;
           while(top>0)
          {
           p=stack[top]  ;/*将右小孩放入栈*/
           top--;
           printf("%c",p->data);
           if(p->rchild!=NULL)
           {top++;
            stack[top]=p->rchild;
           }
            if(p->lchild!=NULL)
           {top++;
            stack[top]=p->lchild;
            }
}
} /* preorder */
void degrees(Bnode *root)/*中序非递归遍历二叉树*/
{   Bnode  *p,*stack[N];
     int top=0,i=0,j=0,k=0;
      p=root;
do{
    while(p!=NULL)
    {
      top++;
      stack[top]=p;
      p=p->lchild;
    }
    if(top>0)
   {
     p=stack[top];/*p所指的 节点为无左子树或其左子树已经遍历过*/
      top--;
      if(p->lchild!=NULL&&p->rchild!=NULL)k++;
     else  if(p->lchild==NULL&&p->rchild==NULL)i++;
      else j++;
     printf("%c",p->data);
     p=p->rchild;
   }
}while(p!=NULL||top!=0);
printf("Dgrees=0:   %d",i);
printf("Dgrees=1:    %d",j);
printf("Dgrees=2:   %d",k);
} /* preorder */

int  nodes(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
  num1=nodes(root->lchild);
  num2=nodes(root->rchild);
  return(num1+num2+1);/*加1是因为要算上根节点*/
}
}
int  nodeO(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
  num1=nodeO(root->lchild);
  num2=nodeO(root->rchild);
  if(root->lchild==NULL&&root->rchild==NULL)
  return(num1+num2+1);/*加1是因为要算上根节点*/
  else  return(num1+num2);
}
}

int  node1(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else if( (root->lchild!=NULL&&root->rchild==NULL) ||(root->lchild==NULL&&root->rchild!=NULL))
  return(1);
else
{
  num1=node1(root->lchild);
  num2=node1(root->rchild);
   return(num1+num2+1 );/*加1是因为要算上根节点*/
    
  }
}
int  node2(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
  num1=node2(root->lchild);
  num2=node2(root->rchild);
  if(root->lchild!=NULL&&root->rchild!=NULL)
  return(num1+num2+1);/*加1是因为要算上根节点*/
  else  return(num1+num2);
}
}
void main(void)      /*主函数*/
    { int j ;
      char CH;  
      Bnode *root;  /* root是指向根结点的指针变量 */
      root=(Bnode *)malloc(sizeof(Bnode ));
do{
      printf("\n1:Create Tree:");
      printf("\n2:Travel Tree:(DLR)");
      printf("\n3:Travel Tree:(LDR)");
      printf("\n4:Travel Tree:(LRD)");
      printf("\n5:Travel Tree:(LDR)(FeiDiGui):");
      printf("\n6:Travel Tree:(DLR)(FeiDiGui):");
      printf("\n7:Degrees  of Tree:(DiGui);");
      printf("\n8:Degrees  of Tree:(FeiDiGui);");
      printf("\nChoose :");
      scanf("%d",&j);
      switch(j){
      case 1:creat_tree(&root);
      break;/* 取根指针变量的地址,生成二叉树 */
      case 2:preorder1(root);    break;   /* 前序遍历二叉树 */
      case 3:preorder2(root);    break;  /* 中序遍历二叉树 */
      case 4:preorder3(root);    break;  /* 后序遍历二叉树 */
      case 5:preorder4(root);    break;  /* 非递归中序遍历二叉树 */
      case 6:preorder5(root);    break;  /* 非递归先序遍历二叉树 */
      case 7:node[3] =nodes(root);
                   printf("SIZE OF TREE=%d",node[3] ) ;  /* 递归算法求节点总数*/
                   node[0] =nodeO(root);
                   printf("Degree=0:%d",node[0] ) ;
                   node[1] =node1(root);
                   printf("Degree=1:%d",node[1] ) ;
                   node[2] =node2(root);
                   printf("Degree=2:%d",node[2] ) ;break;
      case 8: degrees(root); break;
      default:printf("Choose from 1,2,3,4...8");break;
     }
printf("\nCONTINUE?(Y/N)");
while(isspace(CH=getchar()));
}while(CH!='N'||CH!='n');
printf("\nbyebye!");
}

[em16][em16][em16][em16]