樹的後跟序遍歷迭代演算法

『壹』 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

『貳』 請教一下數據結構 二叉樹的先序遍歷 中序遍歷 後序遍歷 是怎麼弄的

所謂先序、中序和後序的區別在於訪問根的時機，分別是BLR、LBR和LRB，其中B、L、R分別表示根結點、根結點的左子樹和根結點的右子樹。
以後序遍歷為例進行講解。

後序遍歷演算法：
(1) 後序遍歷根結點的左子樹；
(2) 後序遍歷根結點的右子樹。
(3) 訪問二叉樹的根結點；

你的方法是將樹分解為根、左子樹、右子樹，再將子樹繼續按前述方法分解，直至每一部分只剩一個結點或空為止。

對該圖，分解為
根(a)，根的左子樹(bde，不分先後)，根的右子樹(cf，不分先後)
故後序的基本順序是(bde)、(cf)、(a)

同樣的道理，對(bde)和(cf)也進行分解：
根(b)、左子樹(d)、右子樹(e) 後序的基本順序是deb
根(c)、左子樹(空)、右子樹(f) 後序的基本順序是fc

整合起來就是：d e b f c a

『叄』 樹的前序遍歷、中序遍歷、後序遍歷詳解

對於當前節點，先輸出該節點，然後輸出他的左孩子，最後輸出他的右孩子。以上圖為例，遞歸的過程如下：
（1）：輸出 1，接著左孩子；
（2）：輸出 2，接著左孩子；
（3）：輸出 4，左孩子為空，再接著右孩子；
（4）：輸出 6，左孩子為空，再接著右孩子；
（5）：輸出 7，左右孩子都為空，此時 2 的左子樹全部輸出，2 的右子樹為空，此時 1 的左子樹全部輸出，接著 1 的右子樹；
（6）：輸出 3，接著左孩子；
（7）：輸出 5，左右孩子為空，此時 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結束。

對於當前結點，先輸出它的左孩子，然後輸出該結點，最後輸出它的右孩子。以上圖為例：
（1）：1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；
（2）：6 的左孩子為空，輸出 6，接著右孩子；
（3）：7 的左孩子為空，輸出 7，右孩子也為空，此時 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
（4）：3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結束。

對於當前結點，先輸出它的左孩子，然後輸出它的右孩子，最後輸出該結點。依舊以上圖為例：
（1）：1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時 4 無左子樹，而 4 的右子樹全部輸出，輸出 4，此時 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時 1 的左子樹全部輸出，接著轉向右子樹；
（2）：3->5，5 無左孩子，也無右孩子，輸出 5，此時 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時 1 的右子樹全部輸出，輸出 1，結束。

已知：
前序遍歷: GDAFEMHZ
中序遍歷: ADEFGHMZ
求後序遍歷
首先，要先畫出這棵二叉樹，怎麼畫呢？根據上面說的我們一步一步來……
1.先看前序遍歷，前序遍歷第一個一定是根節點，那麼我們可以知道，這棵樹的根節點是G，接著，我們看中序遍歷中，根節點一定是在中間訪問的，那麼既然知道了G是根節點，則在中序遍歷中找到G的位置，G的左邊一定就是這棵樹的左子樹，G的右邊就是這棵樹的右子樹了。
2.我們根據第一步的分析，大致應該知道左子樹節點有：ADEF，右子樹的節點有：HMZ。同時，這個也分別是左子樹和右子樹的中序遍歷的序列。
3.在前序遍歷遍歷完根節點後，接著執行前序遍歷左子樹，注意，是前序遍歷，什麼意思？就是把左子樹當成一棵獨立的樹，執行前序遍歷，同樣先訪問左子樹的根，由此可以得到，左子樹的根是D，第2步我們已經知道左子樹是ADEF了，那麼在這一步得到左子樹的根是D，請看第4步。
4.從第2步得到的中序遍歷的節點序列中，找到D，發現D左邊只有一個A，說明D的左子樹只有一個葉子節點，D的右邊呢？我們可以得到D的右子樹有EF，再看前序遍歷的序列，發現F在前，也就是說，F是先前序遍歷訪問的，則得到E是F的左子樹，只有一個葉子節點。
5.到這里，我們可以得到這棵樹的根節點和左子樹的結構了。如下圖：

6.接著看右子樹，在第2步的右子樹中序遍歷序列中，右子樹是HMZ三個節點，那麼先看前序遍歷的序列，先出現的是M，那麼M就是右子樹的根節點，剛好，HZ在M的左右，分別是它的左子樹和右子樹，因此，右子樹的結構就出來了：

7.到這里，我們可以得到整棵樹的結構：

中序遍歷：ADEFGHMZ
後序遍歷：AEFDHZMG

1..根據後序遍歷的特點（左右中），根節點在結尾，確定G是根節點。根據中序遍歷的特點（左中右），確定ADEF組成左子樹，HMZ組成右子樹。

2.分析左子樹。ADEF這四個元素在後序遍歷（左右中）中的順序是AEFD，在中序遍歷（左中右）中的順序是ADEF。根據後序遍歷（左右中）的特點確定D是左子樹的節點，根據中序遍歷（左中右）的特點發現A在D前面，所以A是左子樹的左葉子，EF則是左子樹的右分枝。
EF在後序（左右中）和中序（左中右）的相對位置是一樣的，所以EF關系是左右或者左中，排除左右關系（缺乏節點），所以EF關系是左中。
到此得出左子樹的形狀

3.分析右子樹。HMZ這三個元素在中序遍歷（左中右）的順序是HMZ，在後序遍歷（左右中）的順序是HZM。根據後序遍歷（左右中）的特點，M在尾部，即M是右子樹的節點。再根據中序遍歷（左中右）的特點，確定H（M的前面）是右子樹的左葉子，Z（M的後面）是右子樹的右葉子。

所以右子樹的形狀

『肆』 已知二叉樹的中序遍歷是DBEAFC.前序遍歷是ABDECF.後序遍歷怎麼算

1、首先聲明一個靜態二叉樹節點類，通過該類對象，可以構建一棵二叉樹結構。

『伍』 樹的後序遍歷具體什麼意思呢

樹的後序遍歷是指先依次後序遍歷每棵子樹，然後訪問根結點。當樹用二叉樹表示法(也叫孩子兄弟表示法)存儲時，可以找到唯一的一棵二叉樹與之對應，我們稱這棵二叉樹為該樹對應的二叉樹。那麼根據這個法則可知，樹的後序遍歷序列等同於該樹對應的二叉樹的中序遍歷。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。

⑴訪問結點本身（N），

⑵遍歷該結點的左子樹（L），

⑶遍歷該結點的右子樹（R）。

以上三種操作有六種執行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。

(5)樹的後跟序遍歷迭代演算法擴展閱讀：

二叉樹前序訪問如下：

從根結點出發，則第一次到達結點A，故輸出A;

繼續向左訪問，第一次訪問結點B，故輸出B；

按照同樣規則，輸出D，輸出H；

當到達葉子結點H，返回到D，此時已經是第二次到達D，故不在輸出D，進而向D右子樹訪問，D右子樹不為空，則訪問至I，第一次到達I，則輸出I；

I為葉子結點，則返回到D，D左右子樹已經訪問完畢，則返回到B，進而到B右子樹，第一次到達E，故輸出E；

向E左子樹，故輸出J；

按照同樣的訪問規則，繼續輸出C、F、G。

二叉樹中序訪問如下：

從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；

到達H，H左子樹為空，則返回到H，此時第二次訪問H，故輸出H；

H右子樹為空，則返回至D，此時第二次到達D，故輸出D；

由D返回至B，第二次到達B，故輸出B；

按照同樣規則繼續訪問，輸出J、E、A、F、C、G。

『陸』 先序遍歷和後序遍歷是什麼

1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

(6)樹的後跟序遍歷迭代演算法擴展閱讀：

圖的遍歷演算法主要有兩種，

一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；

另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。

如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。

如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。

利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。

寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：

1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；

2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。

3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；

4、遍歷完所有的頂點而可以重復，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

『柒』 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(7)樹的後跟序遍歷迭代演算法擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

『捌』 知道一棵樹的中序遍歷和後序遍歷，如何推算出這顆樹的前序遍歷

樹中已知先序和中序求後序。
如先序為：abdc,中序為：bdac .
則程序可以求出後序為：dbca 。此種題型也為數據結構常考題型。
演算法思想：先序遍歷樹的規則為中左右，則說明第一個元素必為樹的根節點，比如上例
中的a就為根節點,由於中序遍歷為：左中右，再根據根節點a，我們就可以知道，左子樹包含
元素為：db，右子樹包含元素：c，再把後序進行分解為db和c（根被消去了），然後遞歸的
進行左子樹的求解（左子樹的中序為：db，後序為：db），遞歸的進行右子樹的求解（即右
子樹的中序為：c，後序為：c）。如此遞歸到沒有左右子樹為止。
關於「已知先序和後序求中序」的思考：該問題不可解，因為對於先序和後序不能唯一的確定
中序，比如先序為 ab，後序為ba，我只能知道根節點為a，而並不能知道b是左子樹還是右子樹
，由此可見該問題不可解。當然也可以構造符合中序要求的所有序列。

2004.12.5
*/
#include <stdio.h>
int find(char c,char A[],int s,int e) /**//* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/**//* 其中pre[]表示先序序，pre_s為先序的起始位置，pre_e為先序的終止位置。 */
/**//* 其中in[]表示中序，in_s為中序的起始位置，in_e為中序的終止位置。 */
/**//* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]構成的後序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /**//* 非法子樹，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /**//* 子樹子僅為一個節點時直接輸出並完成。 */<br/> return ;<br/> }
c=pre[pre_s]; /**//* c儲存根節點。 */
k=find(c,in,in_s,in_e); /**//* 在中序中找出根節點的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /**//* 遞歸求解分割的左子樹。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /**//* 遞歸求解分割的右子樹。 */
printf("%c",c); /**//* 根節點輸出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}

//..

已知二叉樹的先序和中序求後序－轉貼自CSDN

二叉樹的根結點（根據三種遍歷）只可能在左右（子樹）之間，或這左子樹的左邊，或右子樹的右邊。
如果已知先序和中序（如果是中序和後序已知也可以，注意：如果是前序和後序的求中序是不可能實現的），先確定這棵二叉樹。
步驟：1，初始化兩個數組，存放先序合中序。
2，對比先序和中序，在中序忠查找先序的第一個元素，則在中序遍歷中將這個元素的左右各元素分成兩部分。即的左邊的部分都在這個元素的左子樹中，右邊的部分都在右子樹中。
3，然後從從先序的第二個元素開始繼續上面的步驟。

如 先序：1 2 3 4 5 6 7 8 9 10 11
後序：3 2 5 4 1 7 9 8 11 10 6

level 1: 1
2: 2 3
3: 3 4 7
4: 5 8
5: 9 10
6: 11

這

『玖』 已知一顆二叉樹的後序遍歷序列和中序遍歷序列確定二叉樹演算法

1. 依據後序遍歷序列的最後一個元素確定根結點T
2. 在中序序列中找到1中確定的根節點，其左邊的序列L為根結點的左子樹結點集合，其右邊的序列R為根結點右子樹結點集合。
3. 將L看做一棵樹的序列集合重復1,得到左子樹的根結點，將R看做一棵樹的序列集合重復1得到右子樹的根結點。這兩個結點即為T的左結點和右結點。
4. 將L看做一棵樹的序列集合重復2得到L子樹的左子樹和右子樹，將R看做一棵樹的序列集合重復2得到R子樹的左子樹和右子樹
5. 對得到的子樹序列重復3，4直到產生的子樹序列都為空為止

『拾』 什麼是先、中、後根遍歷什麼是左子樹、右子樹和二叉樹

1、先根遍歷一般是先序遍歷(Pre-order)，按照根左右的順序沿一定路徑經過路徑上所有的結點。在二叉樹中，先根後左再右。巧記：根左右。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的先根遍歷結果是：ABDECF

6、二叉樹

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。