#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);};
}