实验六：二叉树的递归遍历及其应用
题目：假设二叉树采用二叉链表结构。设计并实现如下算法：后序递归建树，先序非递归遍历该树，输出各个节点的值，并求该树中单分支节点的个数。

代码（TC下编译通过）：


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

#define TRUE            1
#define FALSE           0
#define OK              1
#define ERROR           0
#define INFEASIBLE        -1
#define OVERFLOW        -2


typedef int Status;
typedef char TElemType;/*数据类型*/

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,/*二叉链表节点*/
*BiTree;/*二叉树*/

/********部分基本操作的函数原型********/
Status CreateBiTree(BiTree *T);
Status PreOrderTraverse(BiTree T, Status (*visit)(TElemType e));

Status operate(TElemType e);

/*********************栈**********************/
typedef BiTNode SqStackElemType;

typedef struct
{
int top,base,count;
SqStackElemType container[100];/*ROW*COLUM];*/
}SqStack;

Status InitStack(SqStack *s);
Status StackEmpty(SqStack s);
Status Push(SqStack *s,SqStackElemType e);
Status Pop(SqStack *s,SqStackElemType *e);

/********栈的部分操作定义**********/
Status InitStack(SqStack *s)
{
s->top=-1;
s->base=0;
s->count=0;
}

Status StackEmpty(SqStack s)
{
if(s.count!=0)
{return FALSE;}
return TRUE;
}

Status Push(SqStack *s,SqStackElemType e)
{
s->top++;
s->container[s->top]=e;
s->count++;
return OK;
}

Status Pop(SqStack *s,SqStackElemType *e)
{
if(s->top<s->base)
{return ERROR;}
*e = s->container[s->top];
s->top--;
s->count--;
}
/*********************END栈**********************/

/********部分基本操作的函数定义********/
Status CreateBiTree(BiTree *T)/*后序递归建树*/
{
    TElemType e;
    /*scanf("%c",e);*/
    e=getchar();

    if(e=='#'||e=='\n')
    {
        *T = 0;
    }
    else
    {
        if((*T)=(BiTNode*)malloc(sizeof(BiTNode)))
        {
            (*T)->lchild = 0;
            (*T)->rchild = 0;
        }
        else
        {exit(OVERFLOW);}
       
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));

        (*T)->data = e;

   
    }
    return OK;
}

Status PreOrderTraverse(BiTree T, Status (*visit)(TElemType e))/*先序非递归遍历*/
{
    BiTNode btn;
    SqStack ss;
   
    int count=0;/*特殊变量，用于记录单分支节点个数*/

    InitStack(&ss);
    if(T)
    {
        Push(&ss,*T);

        for(;!StackEmpty(ss);)
        {
            Pop(&ss,&btn);
            (*visit)(btn.data);

            if(btn.rchild)
            {
                Push(&ss,*btn.rchild);
            }
            if(btn.lchild)
            {
                Push(&ss,*btn.lchild);
            }
           
            if((!(btn.rchild&&btn.lchild))&&(btn.rchild||btn.lchild))/*特殊，记录单分支节点个数*/
            {count++;}
        }
    }
    printf("\n%d",count);/*特殊，输出单分支节点个数*/
   
    return OK;
}

Status operate(TElemType e)
{
    printf("%5c",e);
    return OK;
}

/*********main 函数*********/
main()
{
    BiTree bt;
    clrscr();
    CreateBiTree(&bt);
    PreOrderTraverse(bt,operate);
}