二叉树的前序中序后序递归非递归的算法模板.doc

#include <>
#include <>
typedef struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{
T=(struct BiTNode *)malloc(sizeof(struct BiTNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int print(BiTree T)//前序遍历（输出二叉树）
{
if(T==NULL)return 0;
else if(T->lchild==NULL && T->rchild==NULL)return 1;
else return print(T->lchild)+print(T->rchild);
}
void main()//主函数
{
BiTree T;
CreateBiTree(T);
printf("%d\n",print(T));
}
复制代码
算法实现二:
#include<>
#include<>
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
int num=0;
void CreatBiTree(struct BiTNode *&p) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ') p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
CreatBiTree(p->lchild);
CreatBiTree(p->rchild);
}
}
void print(struct BiTNode *p) //前序遍历（输出二叉树）
{
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
else
{
print(p->lchild);
print(p->rchild);
}
}
}
void main()//主函数
{
struct BiTNode *p;
CreatBiTree(p);
print(p);
printf("%d\n",num);
}
复制代码
2、 中序遍历（递归）:
[/code][code]#include<>
#include<>
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //中序遍历（输出二叉树）
{
if(p!=NULL)
{
print(p->lchild);
printf("%c",p->data);
print(p->rchild);
}
else
printf(" ");
}
void main()//主函数
{
struct BiTNode *p;
later(p);
print(p);
}
复制代码
3、 后序遍历（递归）:
[/code][code]#include<>
#include<>
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *