二叉树常用算法

#include"stdio.h"
#include "stdlib.h"
#define PR printf
#define ERROR 0
#define MAX 100


typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}
BTNode;
typedef BTNode *DataType;
typedef struct
{
DataType data[MAX];
int top;
}
SeqStack;
SeqStack *s;

SeqStack *createemptystacks()
{
SeqStack *s;
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top=0;
return s;
}

int stackemptys(SeqStack *s)
{
return s->top==0;
}
int stackfulls(SeqStack *s)
{
return s->top==MAX;
}
void pushs(SeqStack *s,DataType x)
{
if(stackfulls(s))
{
PR("over flow\n");
}
else
{
s->data[s->top++]=x;
}
}
void pops (SeqStack *s)
{
if(stackemptys(s))
{
PR("unde flow\n");
}

else
{
s->top--;
}
}
DataType gettops(SeqStack *s)
{
return s->data[s->top-1];
}
BTNode *createbintree()
{
BTNode *t;
char x;
scanf("%c",&x);
if(x=='#')
t=NULL;
else
{
t=(BTNode *)malloc(sizeof(BTNode));
t->data=x;
t->lchild=createbintree();
t->rchild=createbintree();
}
return (t);
}
//树的遍历
void preorder(BTNode *t)
{
if(t!=NULL)
{
PR("%c\t",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

void inorder(BTNode *t)
{
if(t!=NULL)
{
inorder(t->lchild);
PR("%c\t",t->data);
inorder(t->rchild);
}
}
void postorder(BTNode *t)
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
PR(" %c\t",t->data);
}
}
void inorderl (BTNode *t)
{
SeqStack *st;
BTNode *p;
if(t==NULL)
return;
st=createemptystacks();
p=t;
do{
while(p)
{

pushs(st,p);
p=p->lchild;
}
if (!stackemptys(st))
{
p=gettops(st);
pops(st);
PR("%c",p->data );
p=p->rchild ;
}
}
while(!stackemptys(st)||p);
}


int leaf(BTNode *t,int n) //计算叶子结点的个数
{

if(t!=NULL)
{
if(t->lchild==NULL&&t->rchild==NULL)
n++;
n=leaf(t->lchild,n);
n=leaf(t->rchild,n);
}
return (n);
}


void Exchange(BTNode *t) //交换左右子树
{
if (t)
{
BTNode *temp;
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
Exchange(t->lchild);
Exchange(t->rchild);
}
}

void Display(BTNode *t) //显示左右子树后的整个树
{
PR("\n\n->按先序遍历输出为:\n");
preorder(t);
PR("\n 暗中序遍历输出为：\n");
inorder(t);
PR("\n 按中序遍历输出为;\n");
postorder(t);
}



void main()
{
BTNode *t;
int n=0;
PR("\n-------欢迎进入方敬的二杈树---------\n");
PR("本程序是二杈树的常见算法\n");
PR("请输入一个二杈树，如34#52642#6264#\n");
t=createbintree();
PR("\n\n->> 按先序遍历输出为：\n");
preorder(t);
PR("\n 按中序遍历输出为：\n");
inorder(t);#
PR("\n 按后序遍历输出为：\n ");
postorder(t);
printf("\n\n->> 按中序非遍历输出为：\n");
inorderl(t);
n=leaf(t,n);
PR("\n\n->> 该树的叶子结点数为:%d",n);
PR("\n\n->> 交换

左右子树的二杈树为(如下按三种方式输出):");
Exchange(t);
Display(t);

}