二叉树的先序遍历,中序遍历,后续遍历的实现

先序遍历:

前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

 

遍历顺序：   A->B->D->E->C->F

 

中序遍历:

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，先左后根再右。

 

遍历顺序：   D->E->B->F->C->A（上图）

 

后序遍历:

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根。

遍历顺序：   D->B->E->A->F->C（上图）

 

 

二叉树的先序遍历,中序遍历,后续遍历的实现：

#include <stdio.h>

#include <stdlib.h> 

int i=-1;

typedef struct nodes            //结构体的构建

{

       intdata;                      

       structnodes *z, *y;      //左右指针，

}node;

 

node* tree(int * root)          //利用node结构体和数组构建树

{

       node*p;

       if(root[++i]== 0)p=NULL;  //如果是0代表空节点

       else{

              p       = (node*)malloc(sizeof(node));//从堆取申请

              p->data= root[i];

              p->z    = tree(root);        //递归调用

              p->y    = tree(root);          //递归调用

       }    

       returnp;

}

void xian(node *root)                        //先序遍历

{

       if(root!= 0){

       printf("%d",root->data);

       xian(root->z);

       xian(root->y);      

       }

}

void zhong(node *root)                            //中序遍历

{

       if(root!= 0){

       zhong(root->z);

       printf("%d",root->data);

       zhong(root->y);   

       }

}

void hou(node *root)                        //后序遍历

{

       if(root!= 0){

       hou(root->z);

       hou(root->y);

       printf("%d",root->data);

       }

}

 

void main(void)

{

       inta[]={3,3,4,0,0,5,4,0,0,0,5,5,7,0,0,3,0,0,3,5,3,0,0,2,0,0,7,0,0}; //先序排列的数组

 

       int*b=a;

       node*root=tree(b);    //构建该树

       xian(root);                          //先序遍历

       printf("\n");

       zhong(root);                //中序遍历

       printf("\n");

       hou(root);                           //后序遍历

       printf("\n");

}