php实现二叉树前中后序遍历,求二叉树前序遍历

本文目录一览：

• 1、二叉树的三种遍历，先，中，后遍历
• 2、怎样建立一个二叉树实现二叉树的先序中序后序和遍历？
• 3、请教一下数据结构二叉树的先序遍历中序遍历后序遍历是怎么弄的
• 4、二叉树遍历问题（前序，中序，后序)
• 5、二叉树求前，中，后序遍历
• 6、怎么写二叉树的先序遍历、中序遍历、后序遍历？

二叉树的三种遍历，先，中，后遍历

先序就是先遍历根，再遍历左子树，再遍历右子树。例如上图的先序遍历是：ABCDEFGHK

中序就是先遍历左子树，再遍历根，再右子树。例如上图的中序遍历是：BDCAEHGKF

后序就是先遍历左子树，再右子树，再根。例如上图的后序遍历是：DCBHKGFEA

怎样建立一个二叉树实现二叉树的先序中序后序和遍历？

其实这个程序很简单的。 代码如下：

#includestdio.h

#includemalloc.h

#define MAX_TREE_SIZE  100

typedef struct {

int i;

}TElemType;

typedef struct BiTNode{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

int CreateBiTree(BiTree T)

{

char ch;

scanf(“%c”,ch);

getchar();

if(ch==’ ‘||ch==’\n’)

{

 T=NULL;

}

else{

 T=(BiTNode *)malloc(sizeof(BiTNode));

 T-data=ch;

 CreateBiTree(T-lchild);

 CreateBiTree(T-rchild);

}

return 1;

}//CreateBiTree()

int Visit(char ch)

{

printf(“%c”,ch);

return 1;

}

int PreOrderTraverse(BiTree T,int (* Visit)(char ch))

{

if(T)

{

 if(Visit(T-data))

  if(PreOrderTraverse(T-lchild,Visit))

   if(PreOrderTraverse(T-rchild,Visit)) return 1;

}else return 1;

}

int InOrderTraverse(BiTree T,int (* Visit)(char ch))

{

if(T)

{

  if(InOrderTraverse(T-lchild,Visit))

   if(Visit(T-data))

    if(InOrderTraverse(T-rchild,Visit)) return 1;

}else return 1;

}

int PostOrderTraverse(BiTree T,int(* Visit)(char ch))

{

if(T)

{

 if(PostOrderTraverse(T-lchild,Visit))

  if(PostOrderTraverse(T-rchild,Visit))

   if(Visit(T-data))  return 1;

}else return 1;

}

void  main()

{

BiTree  T;

printf(“从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：\n”);

CreateBiTree(T);

printf(“先序遍历为：”);

PreOrderTraverse(T,Visit);

printf(“\n”);

printf(“中序遍历为：”);

InOrderTraverse(T,Visit);

printf(“\n”);

printf(“后序遍历为：”);

PostOrderTraverse(T,Visit);

}

请教一下数据结构二叉树的先序遍历中序遍历后序遍历是怎么弄的

所谓先序、中序和后序的区别在于访问根的时机，分别是BLR、LBR和LRB，其中B、L、R分别表示根结点、根结点的左子树和根结点的右子树。

以后序遍历为例进行讲解。

后序遍历算法：

(1)后序遍历根结点的左子树；

(2)后序遍历根结点的右子树。

(3)访问二叉树的根结点；

你的方法是将树分解为根、左子树、右子树，再将子树继续按前述方法分解，直至每一部分只剩一个结点或空为止。

对该图，分解为

根(a)，根的左子树(bde，不分先后)，根的右子树(cf，不分先后)

故后序的基本顺序是(bde)、(cf)、(a)

同样的道理，对(bde)和(cf)也进行分解：

根(b)、左子树(d)、右子树(e)后序的基本顺序是deb

根(c)、左子树(空)、右子树(f)后序的基本顺序是fc

整合起来就是：debfca

二叉树遍历问题（前序，中序，后序)

前序遍历（DLR）

前序遍历也叫做先根遍历，可记做根左右。

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则：

（1）访问根结点

（2）前序遍历左子树

（3）前序遍历右子树

注意的是：遍历左右子树时仍然采用前序遍历方法。

中序遍历（LDR）

中序遍历也叫做中根遍历，可记做左根右。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：

若二叉树为空则结束返回，否则：

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树。

注意的是：遍历左右子树时仍然采用中序遍历方法。

后序遍历（LRD）

后序遍历也叫做后根遍历，可记做左右根。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：

若二叉树为空则结束返回，否则：

（1）后序遍历左子树。

（2）后序遍历右子树。

（3）访问根结点。

注意的是：遍历左右子树时仍然采用后序遍历方法。

如上图所示二叉树

前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树

遍历结果：a,b,e,f,c,g

中序遍历，也叫中根遍历，顺序是

左子树，根，右子树

遍历结果：e,b,f,a,g,c

后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根

遍历结果：e,f,b,g,c,a

二叉树求前，中，后序遍历

是不是算法？

这是递归算法

void PreOrder(BiTree T){//先序遍历

if(T==NULL)

return ;

printf(T-data);

PreOrder(T-lchild);

PreOrder(T-rchild);

}

void InOrder(BiTree T){//中序遍历

if(T==NULL)

return ;

InOrder(T-lchild);

printf(T-data);

InOrder(T-rchild);

}

void PostOrder(BiTree T){//后序遍历

if(T==NULL)

return ;

PostOrder(T-lchild);

PostOrder(T-rchild);

printf(T-data);

}

怎么写二叉树的先序遍历、中序遍历、后序遍历？

一、

先序遍历

：

1、访问根节点

2、

前序遍历

左

子树

3、前序遍历

右子

树

二、

中序遍历

：

1、中序遍历左子树

2、访问根节点

3、中序遍历右子树

三、

后序

遍历：

1、

后序遍历

左子树

2、后序遍历右子树

3、访问根节点

下面介绍一下例子与方法：

1、画树求法：

第一步，根据前序遍历的特点，我们知道

根结点

为G

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1

确定根,确定左子树，确定右子树。

2

在左子树中递归。

3

在右子树中递归。

4

打印当前根。

那么，我们可以画出这个

二叉树

的形状：

那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG

二叉树的一些介绍：

在计算机科学中，二叉树是每个节点最多有两个子树的

树结构

。通常子树被称作“左子树”（left

subtree）和“右子树”（right

subtree）。二叉树常被用于实现

二叉查找树

和

二叉堆

。

二叉树的每个结点至多只有二

棵子

树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为

满二叉树

；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为

完全二叉树

。