求出一个排序二叉树中结点度数为一的结点个数

#include<stdio.h>

#include<iostream.h>

#include<conio.h>

#include<malloc.h>

#include<stdlib.h>

#define ERROR 0

#define STACK_INIT_SIZE 100

#define OVERFLOW -1

#define FALSE 0

#define TRUE 1

#define OK 1

int i=0;

struct tree{

char data;

struct tree *Lchild,*Rchild;

};

typedef struct tree SElemType;

typedef int Status ;

struct STACK

{

SElemType *base;

SElemType *top;

int stacksize;

};

typedef struct STACK *pSqstack;

typedef struct STACK SqStack;

Status InitStack(SqStack **S)

{

(*S)=(SqStack *)malloc(sizeof(SqStack));

(*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));

if(!(*S)->base) exit (OVERFLOW);

(*S)->top=(*S)->base;

(*S)->stacksize=STACK_INIT_SIZE;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.top==S.base) return TRUE;

else

return FALSE;

}

Status Push(SqStack *S,SElemType e)

{

*(S->top++)=e;

return OK;

}

Status Pop(SqStack *S,SElemType *e)

{

if(S->top==S->base) return ERROR;

e=--S->top;

return OK;

}

void Visite(struct tree *t)

{

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

}

struct tree *create_btree(struct tree *t,struct tree *r,char data)//创建二叉树

{

if (r ==0 )

{

r=new (struct tree);

if ( r == 0)

{

printf("Out of memory/n"); return 0 ;

}

r->Lchild= 0; r->Rchild=0; r->data=data;

if (t)

{

if(data<t->data) t->Lchild=r;

else

t->Rchild=r;

}

else

{

r->Rchild=0; r->Lchild = 0;

}

return r;

}

if(data<r->data)

create_btree(r,r->Lchild,data);

else

create_btree(r,r->Rchild,data);

return t;

}

void PreOrderUnrec(struct tree *t,SqStack *s)//前序遍历二叉树

{

InitStack(&s);

struct tree *p,*q;

p=t;

while (p!=0||!StackEmpty(*s))

{

while (p!=0) //遍历左子树

{

Visite(p);

if((p->Lchild==0||p->Rchild==0)&&(p->Lchild!=p->Rchild))

{printf(" o ");

i++;};

Push(s,*p);

p=p->Lchild;

};//endwhile

while (!StackEmpty(*s)) //通过下一次循环中的内嵌while实现右子树遍历

{

Pop(s,p);

q=s->top;

//Pop(s,p);

p=q->Rchild;

Visite(p);

printf("?");

};//endif

};//endwhile

}//PreOrderUnrec

void main()

{

char s[100], e;

SqStack *Sa;

struct tree *t=0;

printf("Input a letter for Creating the Binary_Tree ( Directly press <Enter> to stop ):/n");

while (*s){

printf("/nInput a letter: ");

e=getch(); /*#include<conio.h>*/

putch(e); /*#include<conio.h>*/

if(e==13) break;

if (!t)

t=create_btree(t,t,e);

else

create_btree(t,t,e);

};

printf("/n");

PreOrderUnrec(t,Sa);

printf("度数为一的结点数为：%d",i);

printf("结束请按q！");

if(getchar()=='q') printf("再见");

else {while(1);};

}