二叉樹前序遍歷演算法

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

所謂先序、中序和後序的區別在於訪問根的時機，分別是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)訪問根結點；
(3)中序遍歷右子樹。
2．先序（前序）遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 先序遍歷左子樹；
(3) 先序遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)後序遍歷左子樹；
(2)後序遍歷右子樹；
(3)訪問根結點

④ 二叉樹的遍歷

遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷結點的左子樹；
(2)訪問當前結點；
(3)遍歷結點的右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問當前結點；
(2) 遍歷結點的左子樹；
(3) 遍歷結點的右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷結點的左子樹；
(2)遍歷結點的右子樹；
(3)訪問當前結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
還有什麼不明白的請繼續追加~

⑤ 求c#前中後序遍歷二叉樹的演算法及思想

下面簡單介紹一下幾種演算法和思路：
先序遍歷：
1. 訪問根結點
2. 按先序遍歷左子樹;
3. 按先序遍歷右子樹;
4. 例如：遍歷已知二叉樹結果為：A->B->D->G->H->C->E->F
中序遍歷：
1. 按中序遍歷左子樹;
2. 訪問根結點;
3. 按中序遍歷右子樹;
4. 例如遍歷已知二叉樹的結果：B->G->D->H->A->E->C->F
後序遍歷：
1. 按後序遍歷左子樹;
2. 按後序遍歷右子樹;
3. 訪問根結點;
4. 例如遍歷已知二叉樹的結果：G->H->D->B->E->F->C->A
層次遍歷：
1.從上到下,從左到右遍歷二叉樹的各個結點(實現時需要借輔助容器);
2.例如遍歷已知二叉樹的結果：A->B->C->D->E->F->G->H

附加代碼：
二叉遍歷演算法解決方案
using System;
using System.Collections.Generic;
using System.Text;
namespace structure
{
class Program
{
二叉樹結點數據結構的定義#region 二叉樹結點數據結構的定義
//二叉樹結點數據結構包括數據域,左右結點以及父結點成員;
class nodes<T>
{
T data;
nodes<T> Lnode, Rnode, Pnode;
public T Data
{
set { data = value; }
get { return data; }

}
public nodes<T> LNode
{
set { Lnode = value; }
get { return Lnode; }
}
public nodes<T> RNode
{
set { Rnode = value; }
get { return Rnode; }

}

public nodes<T> PNode
{
set { Pnode = value; }
get { return Pnode; }

}
public nodes()
{ }
public nodes(T data)
{
this.data = data;
}

}
#endregion

#region 先序編歷二叉樹
static void PreOrder<T>(nodes<T> rootNode)
{
if (rootNode != null)
{
Console.WriteLine(rootNode.Data);
PreOrder<T>(rootNode.LNode);
PreOrder<T>(rootNode.RNode);

}
}

#endregion

⑥ 二叉樹先序遍歷流程圖怎麼畫

首先要搞明白二叉樹的幾種遍歷方法：（1）、先序遍歷法：根左右；（2）、中序遍歷法：左根右；（3）、後序遍歷法：左右根。其中根：表示根節點；左：表示左子樹；右：表示右子樹。
至於談到如何畫先序遍歷的流程圖，可以這樣考慮：按照遞歸的演算法進行遍歷一棵二叉樹。
程序首先訪問根節點，如果根節點的值為空（NULL），則停止訪問；如果根節點的值非空，則遞歸訪問二叉樹的左子樹（left），然後是依然判斷二叉樹下面的左子樹下面的根節點是否為空（NULL），如果根節點的值為空（NULL），則返回上一層，再訪問二叉樹的右子樹（right）。
依此類推。

⑦ C++中二叉樹的前序（後序、中序）遍歷分別是什麼意思相應的樹圖怎麼看

二叉樹的遍歷是指按照一定次序訪問樹中所有結點，並且每個節點僅被訪問一次的過程。

1、先序遍歷（前序）

（1）訪問根節點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹。

2、中序遍歷

（1）中序遍歷左子樹；

（2）訪問根節點；

（3）中序遍歷右子樹。

3、後序遍歷

（1）後序遍歷左子樹；

（2）後序遍歷右子樹『

（3）訪問根節點。

記住訪問根結點的時機就可以區分三種遍歷方法了。

同時知道一棵二叉樹的先序序列和中序序列，或者同時知道中序序列和後序序列，就能確定這棵二叉樹的結構。構造演算法相信你已經學習過，在任一本介紹數據結構的書上應該也有描述的。由於涉及到演算法細節，這里就不細說了。

下面根據你例子中給出的序列來介紹確定二叉樹結構的步驟：

（1）後序序列中最後一個為樹的根節點，即c為二叉樹的根結點；

（2）中序遍歷中根節點把序列分為左右子樹的中序遍歷序列兩個部分，在你的例子在右子樹沒有中序遍歷序列（中序遍歷序列中c右邊沒有序列），故可知二叉樹的左子樹的後序遍歷序列為dabe，中序遍歷序列為deba；

（3）應用（1）的方法，確定c的左子樹的根結點為e，並把以e為根結點的子樹的中序遍歷序列劃分為d（以e為根結點的左子樹的中序遍歷序列）和ba（以e為根結點的右子樹的中序遍歷序列）兩個部分，後序遍歷序列為dab；

（4）應用（1）的方法，可確定e的左結點為b；

（5）應用（1）的方法，可確定e的右結點為a；

（6）最後，可確定a無左結點，右結點為d。

構造的二叉樹如圖中所示。

那麼可獲得前序遍歷序列為cedba

⑧ 二叉樹的遍歷

1．遍歷方案 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作： （1）訪問結點本身(N)， （2）遍歷該結點的左子樹(L)， （3）遍歷該結點的右子樹(R)。以上三種操作有六種執行次序： NLR、LNR、LRN、NRL、RNL、RLN。 注意： 前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。 2．三種遍歷的命名 根據訪問結點操作發生位置命名： ① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷)) ——訪問結點的操作發生在遍歷其左右子樹之前。 ② LNR：中序遍歷(InorderTraversal) ——訪問結點的操作發生在遍歷其左右子樹之中(間)。 ③ LRN：後序遍歷(PostorderTraversal) ——訪問結點的操作發生在遍歷其左右子樹之後。 注意： 由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。 遍歷演算法 1．中序遍歷的遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1)遍歷左子樹； (2)訪問根結點； (3)遍歷右子樹。 2．先序遍歷的遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1) 訪問根結點； (2) 遍歷左子樹； (3) 遍歷右子樹。 3．後序遍歷得遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結點。 ~

⑨ 二叉樹前序遍歷法舉例!急急急！！！

二叉樹的三種金典遍歷法

1.前序遍歷法：

前序遍歷（DLR）

前序遍歷（DLR）

前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

若二叉樹為空則結束返回，否則：

（1）訪問根結點

（2）前序遍歷左子樹

（3）前序遍歷右子樹

注意的是：遍歷左右子樹時仍然採用前序遍歷方法。

如上圖所示二叉樹

前序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹

遍歷結果：ABDECF

中序遍歷，也叫中根遍歷，順序是左子樹，根，右子樹

遍歷結果：DBEAFC

後序遍歷，也叫後根遍歷，遍歷順序，左子樹，右子樹，根

遍歷結果：DEBFCA

2.中序遍歷法：

中序遍歷

中序遍歷（LDR）

中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。即：

若二叉樹為空則結束返回，否則：

（1）中序遍歷左子樹

（2）訪問根結點

（3）中序遍歷右子樹。

注意的是：遍歷左右子樹時仍然採用中序遍歷方法。

3.後序遍歷法：

後序遍歷

簡介

後序遍歷是二叉樹遍歷的一種。後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹三者中，首先遍歷左子樹，然後遍歷右子樹，最後遍歷訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。後序遍歷有遞歸演算法和非遞歸演算法兩種。

遞歸演算法

演算法描述：

（1）若二叉樹為空，結束

（2）後序遍歷左子樹

（3）後序遍歷右子樹

（4）訪問根結點

偽代碼

PROCEDUREPOSTRAV(BT)

IFBT<>0THEN

{

POSTRAV(L(BT))

POSTRAV(R(BT))

OUTPUTV(BT)

}

RETURN

c語言描述

structbtnode

{

intd;

structbtnode*lchild;

structbtnode*rchild;

};

voidpostrav(structbtnode*bt)

{

if(bt!=NULL)

{

postrav(bt->lchild);

postrav(bt->rchild);

printf("%d",bt->d);

}

}

非遞歸演算法

演算法1（c語言描述）：

voidpostrav1(structbtnode*bt)

{

structbtnode*p;

struct

{

structbtnode*pt;

inttag;

}st[MaxSize];

}

inttop=-1;

top++;

st[top].pt=bt;

st[top].tag=1;

while(top>-1)/*棧不為空*/

{

if(st[top].tag==1)/*不能直接訪問的情況*/

{

p=st[top].pt;

top--;

if(p!=NULL)

{

top++;/*根結點*/

st[top].pt=p;

st[top].tag=0;

top++;/*右孩子結點*/

st[top].pt=p->p->rchild;

st[top].tag=1;

top++;/*左孩子結點*/

st[top].pt=p->lchild;

st[top].tag=1;

}

}

if(st[top].tag==0)/*直接訪問的情況*/

{

printf("%d",st[top].pt->d);

top--;

}

}

}

演算法2：

voidpostrav2(structbtnode*bt)

{

structbtnode*st[MaxSize],*p;

intflag,top=-1;

if(bt!=NULL)

{

do

{

while(bt!=NULL)

{

top++;

st[top]=bt;

bt=bt->lchild;

}

p=NULL;

flag=1;

while(top!=-1&&flag)

{

bt=st[top];

if(bt->rchild==p)

{

printf("%d",bt->d);

top--;

p=bt;

}

else

{

bt=bt->rchild;

flag=0;

}

}

}while(top!=-1)

printf(" ");

}

}

老曹回答必屬佳作記得給分謝謝合作！

⑩ 寫出二叉樹的先序遍歷、中序遍歷、後序遍歷。

一、先序遍歷：

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