如何根據兩種遍歷方法判斷二叉樹

『壹』 知道二叉樹兩種遍歷 求第三種遍歷 該用什麼方法

• 由兩種遍歷所得的順序能唯一確定一棵二叉樹，

• 比如給定了一顆二叉樹的先序序列是:ABDECFG,中序序列是：DBEAFCG，

1. 由先序序列可以確定該二叉樹根為A,因為先序遍歷的順序是從根到左子樹再到右子樹，然後從中序序列中，可以得知DBE在A的左子樹，而FCG在A的右子樹，

2. 由於在先序序列中B緊跟在A後，所以B肯定是A左子樹的樹根，再看中序序列里，A的左子樹是DBE，由中序序列遍歷的順序為：左子樹，雙親，右子樹，可知D為B的左子樹，E為B的右子樹，

3. 同樣可以分析樹根A的右子樹，先序序列中ABDE已經將樹根和左子樹遍歷完成，所以剩下的CFG是右子樹的先序遍歷序列，可知C為右子樹的樹根，F為C的左子樹，G為C的右子樹，所以

4. 該二叉樹按層序遍歷的順序應該是ABCDEFG。

『貳』 如何根據後序遍歷和中序遍歷建立二叉樹

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define SIZE 100

typedef char ElemType;

//聲明二叉樹結構體

typedef struct node

{

ElemType data;

struct node *lchild,*rchild;

}BitTree;

BitTree *createBinTreeByPostIn(char *post,char *in,int number)

{

if(number==0) return NULL;

char c = post[number-1];

int i = 0;

while(in[i]!=c && i < number)i++;

int leftNumber = i;

int rightNumber = number - i - 1;

BitTree *node = (BitTree *)malloc(sizeof(BitTree));

node->data = c;

node->lchild = createBinTreeByPostIn(&post[0],&in[0],leftNumber);

node->rchild = createBinTreeByPostIn(&post[leftNumber],&in[i+1],rightNumber);

return node;

}

void PreOrder(BitTree *bt)

{

if(bt!=NULL)

{

printf("%c ",bt->data);

PreOrder(bt->lchild);

PreOrder(bt->rchild);

}

}

int main(int argc,char **argv)

{

char a[SIZE],b[SIZE];

BitTree *p;

while(scanf("%s%s",a,b)!=EOF)

{

p = createBinTreeByPostIn(a,b,strlen(a));

PreOrder(p);

printf(" ");

}

return 0;

}

(2)如何根據兩種遍歷方法判斷二叉樹擴展閱讀：

注意事項

一、中序遍歷（LDR）

中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。即：
若二叉樹為空則結束返回，否則：

1、中序遍歷左子樹

2、訪問根結點

3、中序遍歷右子樹。

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

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

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

1、後序遍歷左子樹。

2、後序遍歷右子樹。

3、訪問根結點。

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

『叄』 怎樣根據先序和後序遍歷確定二叉樹

根據二叉樹遍歷公式：
前序遍歷：根—左—右
後續遍歷：左—右—根
首先確定根，依次再確定各個結點！

『肆』 二叉樹，如何從兩種遍歷的結果推出另一種遍歷方法簡單詳細一點。注意不是編程求解

這個問題呢其實很簡單，去年考試我們就考到了
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
比如你知道一個程序的先序遍歷是ABCDEFG 中序遍歷是CBDAEGF讓你推算出後序遍歷
因為先序遍歷的順序是根-左-右 那麼我們看先序遍歷ABCDEFG，那麼A就是根
再看中序遍歷CBDAEGF，根據中序遍歷的左-根-右 看出A左邊CBD的都是左子樹，右邊的EGF是左子樹
然後對先序遍歷劃分 A/BCD/EFG
對左子樹CBD 由先序遍歷中的A/BCD/EFG可以看出BCD中B在前面 則B是左子樹的根 C是下一行的左子樹
同理可對EFG分析
那麼畫出圖 A
/ \
B E
/\ \
C D F
/
G
那麼後序遍歷CDBGFEA
我當初也學了一段時間，比較繞是吧
我在這寫了半天 不知道你能看懂不
不行的加我Q

『伍』 怎麼根據二叉樹的兩個遍歷算出另一個遍歷，有什麼技巧

用遞歸法可畫出二叉樹圖然後看圖寫出你要的遍歷哈，下面我給你講下哈（好理解的）：

假設有棵樹，長下面這個樣子，它的前序遍歷，中序遍歷，後續遍歷都很容易知道。

PreOrder: GDAFEMHZ
InOrder: ADEFGHMZ
PostOrder: AEFDHZMG

現在，假設僅僅知道前序和中序遍歷，如何求後序遍歷呢看比如，已知一棵樹的前序遍歷是地GDAFEMHZ地，而中序遍歷是地ADEFGHMZ地應該如何求後續遍歷?

第一步，root最簡單，前序遍歷的第一節點G就是root。

第二步，繼續觀察前序遍歷GDAFEMHZ，除了知道G是root，剩下的節點必然是root的左右子樹之外，沒法找到更多信息了。

第三步，那就觀察中序遍歷ADEFGHMZ。其中root節點G左側的ADEF必然是root的左子樹，G右側的HMZ必然是root的右子樹。

第四步，觀察左子樹ADEF，左子樹的中的根節點必然是大樹的root的leftchild。在前序遍歷中，大樹的root的leftchild位於root之後，所以左子樹的根節點為D。

第五步，同樣的道理，root的右子樹節點HMZ中的根節點也可以通過前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節點遍歷完之後才會遍歷右子樹，並且遍歷的右子樹的第一個節點就是右子樹的根節點。
如何知道哪裡是前序遍歷中的左子樹和右子樹的分界線呢看通過中序遍歷去數節點的個數。
在上一次中序遍歷中，root左側是A、D、E、F，所以有4個節點位於root左側。那麼在前序遍歷中，必然是第1個是G，第2到第5個由A、D、E、F過程，第6個就是root的右子樹的根節點了，是M。

第六步，觀察發現，上面的過程是遞歸的。先找到當前樹的根節點，然後劃分為左子樹，右子樹，然後進入左子樹重復上面的過程，然後進入右子樹重復上面的過程。最後就可以還原一棵樹了。
第七步，其實，如果僅僅要求寫後續遍歷，甚至不要專門佔用空間保存還原後的樹。只需要稍微改動第六步，就能實現要求。僅需要把第六步的遞歸的過程改動為如下:
1 確定根,確定左子樹，確定右子樹。
2 在左子樹中遞歸。
3 在右子樹中遞歸。
4 列印當前根。

我上面給你找出了一部分，你只要重復我上面的方法就可以找出其他的，加油，慢慢體會，你行的，不清楚再問我。

『陸』 如何根據前序遍歷序列和中序遍歷序列確定二叉樹

前序遍歷:1 2 4 8 9 10 11 5 3 6 7 (規律：根在前；子樹在根後且左子樹比右子樹靠前)； 中序遍歷:8 4 10 9 11 2 5 1 6 3 7 (規律：根在中；左子樹在跟左邊，右子樹在根右邊)； 後序遍歷:8 10 11 9 4 5 2 6 7 3 1 (規律：根在後；子樹在根前且左...

『柒』 怎樣通過二叉樹的遍歷來確定一棵樹

索路徑:

先根(次序)遍歷:

若樹不空，則先訪問根結點，然後依次先根遍歷各棵子樹。

後根(次序)遍歷:

若樹不空，則先依次後根遍歷各棵子樹，然後訪問根結點。

按層次遍歷:

若樹不空，則自上而下自左至右訪問樹中每個結點。

森林的遍歷

先序遍歷(對森林中的每一棵樹進行先根遍歷)

若森林不空，則

訪問森林中第一棵樹的根結點;

先序遍歷森林中第一棵樹的子樹森林;

先序遍歷森林中(除第一棵樹之外)其餘樹構成的森林。

中序遍歷(對森林中的每一棵樹進行後根遍歷)

若森林不空，則

中序遍歷森林中第一棵樹的子樹森林;

訪問森林中第一棵樹的根結點;

中序遍歷森林中(除第一棵樹之外)其餘樹構成的森林。
另外,虛機團上產品團購,超級便宜

『捌』 知道二叉樹遍歷怎樣畫出二叉樹

由兩種遍歷所得的順序能唯一確定一棵二叉樹，比如給定了一顆二叉樹的先序序列是:ABDECFG,中序序列是：DBEAFCG，由先序序列可以確定該二叉樹根為A,因為先序遍歷的順序是從根到左子樹再到右子樹，然後從中序序列中，可以得知DBE在A的左子樹，而FCG在A的右子樹，由於在先序序列中B緊跟在A後，所以B肯定是A左子樹的樹根，再看中序序列里，A的左子樹是DBE，由中序序列遍歷的順序為：左子樹，雙親，右子樹，可知D為B的左子樹，E為B的右子樹，同樣可以分析樹根A的右子樹，先序序列中ABDE已經將樹根和左子樹遍歷完成，所以剩下的CFG是右子樹的先序遍歷序列，可知C為右子樹的樹根，F為C的左子樹，G為C的右子樹，所以該二叉樹按層序遍歷的順序應該是ABCDEFG。

『玖』 如何根據後序遍歷和中序遍歷建立二叉樹

這里的「先根」也叫做先序，「中」和「後」也一樣。
先序遍歷是先訪問當前節點，然後再遍歷左子樹，最後是右子樹。
中序遍歷是先遍歷左子樹，再訪問當前節點，最後是右子樹。
後序遍歷是先遍歷左子樹，再遍歷右子樹，最後訪問當前節點。
例：
一棵二叉樹的先根遍歷為abcdefg，中根遍歷為cbdeagf，則其後根遍歷為
：
1、先序遍歷的第一個當前節點一定是根節點，所以a是根
2、由於中序遍歷是先遍歷完左子樹再訪問當前節點，所以可以看出中序序列在a之前的都是a的左子樹中的節點，而在a之後是a的右子樹的節點。
3、這樣就分成了（cbde）a
(gf),三個集合。
4、我們分別再看各個集合。cbde集合中最先在先序序列中出現的是b，這說明b在這個集合中應該是第一個出現的。所以右可以再分
********a
**b********(gf)
c**(de)
5、再看de，在先序序列中因為d在e前方，所以d肯定是e的父節點，現在剩下的就是判斷e是d的左孩子還是右孩子。從中序序列中看，d仍然是在e的前方，說明e是d的右孩子。
********a
**b********(gf)
c***d
******e
6、最後剩下gf.和de相似的判斷方法，在先序序列中f在g前方，說明f是父節點，而在中序當中g在f前方，說明g是f的左孩子。
所以這顆二叉樹應該是
********a
**b********f
c***d*****g
******e
7、二叉樹出來了，後序的原理最上方講了，剩下的就好辦了。先左孩子，然後右孩子，最後當前節點。
8、當前節點為a時由於左右兩個子樹還沒有訪問所以要先訪問完左右子樹才能訪問a.
9、b同a
10、c沒有左右孩子，所以它是第一個。
11、c訪問完了在訪問b的右子樹。
12、先訪問d的孩子e,然後再是d。
13、b的左右孩子都訪問完了，所以下一個是b。
14、訪問完b，a的左子樹訪問完了，但是還是不能訪問a，因為a的右子樹還沒有訪問。
15、a的右子樹中，g是f的孩子，所以先g再f。
16、最後是根節點a。