#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define NULL 0
typedef struct BiTNode{
char data1;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct QNode {
BiTree data2;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
typedef struct{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base=(BiTree *)malloc(STACK_INIT_SIZE *sizeof(BiTree));
if(!S.base) return 0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}//InitStack
int Push(SqStack &S,BiTree e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));
if(!S.base) return 0;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}//Push
int Pop(SqStack &S,BiTree &e)
{
if(S.top==S.base) return 0;
e=*--S.top;
return 1;
}//Pop
int StackEmpty(SqStack S)
{
if(S.top==S.base) return 1;
else return 0;
}
int InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) return 0;
Q.front->next=NULL;
Q.rear=Q.front;
return 1;
}
int EnQueue(LinkQueue &Q, BiTree e)
{ QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) return 0;
p->data2=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
int DeQueue(LinkQueue &Q,BiTree &e)
{ QueuePtr p;
if(Q.front==Q.rear) return 0;
p=Q.front->next;
e=p->data2;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return 1;
}
int QueueEmpty (LinkQueue Q)
{
if(Q.front==Q.rear) return 1;
else return 0;
}
void CreatBiTree(BiTree &bt)
{//根据输入的字符建立二叉树bt的二叉链表
char ch;
scanf("%c",&ch);
if(ch==' ') bt=NULL;
else{
bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->data1=ch;
CreatBiTree(bt->lchild);
CreatBiTree(bt->rchild);
}
}//CreatBiTree
void visit(char e)
{ printf("%2c",e); }
void PreOrderTraverse(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行先序遍历
if(bt)
{ visit(bt->data1); //访问根结点
PreOrderTraverse(bt->lchild);
PreOrderTraverse(bt->rchild);
}
}// PreOrderTraverse
void PreOrderTraverse1(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行先序遍历
SqStack S; BiTree p;
if(bt)
{
InitStack(S); p=bt; Push(S,bt );
while(!StackEmpty(S))
{ printf("%2c",p->data1);
if(p->rchild) Push(S, p->rchild);
if(p->lchild) p=p->lchild;
else Pop(S, p);
}//while
}//if
}// PreOrderTraverse
void InOrderTraverse(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行中序遍历
if(bt)
{ InOrderTraverse(bt->lchild);
visit(bt->data1); //访问根结点
InOrderTraverse(bt->rchild);
}
}// InOrderTraverse
void InOrderTraverse1(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行中序遍历
SqStack S; BiTree p;
if(bt){
InitStack(S); p=bt;
while(p || ! StackEmpty (S))
if(p)
{ Push(S, p); p=p->lchild;}
else
{ Pop(S, p); printf("%2c",p->data1);
p=p->rchild;
}
}//if
}// InOrderTraverse
void PostOrderTraverse(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行后序遍历
if(bt)
{ PostOrderTraverse(bt->lchild);
PostOrderTraverse(bt->rchild);
visit(bt->data1); //访问根结点
}
}// PostOrderTraverse
void PostOrderTraverse1(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行后序遍历
SqStack S; BiTree p,q;
InitStack(S); Push(S, NULL); p=bt; q=NULL;
while (p || !StackEmpty(S))
{ if (p && p!=q)
{ Push(S, p); p=p->lchild; }
else
{ Pop(S,p);
if (!StackEmpty(S))
if (p->rchild && p->rchild!=q)
{ Push(S,p); p=p->rchild; }
else { printf("%2c",p->data1); q=p; }
}
}
}//PostOrderTraverse
void LevelOrderTraverse(BiTree bt)
{//二叉树bt采用二叉链表存储，对bt进行层次遍历
LinkQueue Q;
if(bt)
{ InitQueue(Q); EnQueue(Q, bt);
while (!QueueEmpty(Q))
{ DeQueue(Q, bt);
printf("%2c",bt->data1);
if (bt->lchild) EnQueue(Q, bt->lchild);
if (bt->rchild) EnQueue(Q, bt->rchild);
}
}
}//LevelOrderTraverse
void CountNumber(BiTree bt)
{ LinkQueue Q;
int count1,count2;
count1=count2=0;
if(bt)
{
InitQueue(Q);EnQueue(Q,bt);count2=1;
while(!QueueEmpty(Q))
{
DeQueue(Q,bt);
if(bt->lchild==NULL&&bt->rchild==NULL)
count1++;
else
{
if(bt->lchild)
{
count2++;
EnQueue(Q,bt->lchild);
}
if(bt->rchild)
{
count2++;
EnQueue(Q,bt->rchild);
}
}
}//while
printf("\n叶子节点是%d,总节点是%d\n",count1,count2);
}
}//CountNumber
void main()
{
BiTree bt;
printf("按先序序列建立二叉树\n");
CreatBiTree(bt);
printf("按递归函数先序遍历二叉树\n");
PreOrderTraverse( bt);
printf("\n按非递归函数先序遍历二叉树\n");
PreOrderTraverse1( bt);
printf("\n按递归函数中序遍历二叉树\n");
InOrderTraverse( bt);
printf("\n按非递归函数中序遍历二叉树\n");
InOrderTraverse1( bt);
printf("\n按递归函数后序遍历二叉树\n");
PostOrderTraverse( bt);
printf("\n按非递归函数后序遍历二叉树\n");
PostOrderTraverse1( bt);
printf("\n层次遍历二叉树\n");
LevelOrderTraverse(bt);
CountNumber( bt);
}
评论0