遍历算法
1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)访问根结点；
(3)遍历右子树。
2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1) 访问根结点；
(2) 遍历左子树；
(3) 遍历右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)遍历右子树；
(3)访问根结点。
实现代码：
#include "stdio.h"
#include "malloc.h"
#define M 100
typedef struct node
{ /* 链式存储的指针类型和结点定义 */
char data;
struct node *lchild,*rchild;
}BTnode;
BTnode *create()/*建立二叉树*/
{
BTnode *t;
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{t=(BTnode *)malloc(sizeof(BTnode)) ;
t->data=ch;
t->lchild=create();
t->rchild=create();
}
return t;
}
void preorder(BTnode *t)/*先序遍历二叉树*/
{
if(t!=NULL)
printf("%c ",t->data);
if(t->lchild!=NULL)
preorder(t->lchild);
if(t->rchild!=NULL)
preorder(t->rchild);
}
void inorder(BTnode *t)/*中序遍历二叉树*/
{
if(t!=NULL)
{
if(t->lchild!=NULL)
inorder(t->lchild);
printf("%c ",t->data);
if(t->rchild!=NULL)
inorder(t->rchild);
}
}
void postorder(BTnode *t)/*后序遍历二叉树*/
{
if(t!=NULL)
{ if(t->lchild!=NULL)
postorder(t->lchild);
if(t->rchild!=NULL)
postorder(t->rchild);
printf("%c ",t->data);
}
}
void main()
{
BTnode *t;
printf("Input data:") ;
t=create();
printf("==================The result==========================/n");
printf("The preorder is:/n");
preorder(t);
printf("/n");
printf("The inorder is:/n");
inorder(t);
printf("/n");
printf("The postorder is:/n");
postorder(t);
printf("/n");
getch();
}
例如：
A
/ /
B C
/ / /
D E F
输入：ABD###CE##F##
先序遍历输出：A B D C E F
中序遍历输出：D B A E C F
后序遍历输出：D B E F C A |
转播
