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的節點對應時，稱之為

完全二叉樹

。