下载文档原格式
二叉树的前序遍历、中序遍历、后续遍历
（递归法）
1、前序遍历（递归）：
算法实现一：
#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);
}
#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);
}
#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);
print(p->rchild);
printf("%c",p->data);
}
else
printf(" ");
}
void main()//主函数
{/*检测：printf("到了吗");*/
struct BiTNode *p;
later(p);
print(p);
}
