1樓:
1、先序遍歷也叫做先根遍歷、前序遍歷,可記做根左右(二叉樹父結點向下先左後右)。
首先訪問根結點然後遍歷左子樹,最後遍歷右子樹。在遍歷左、右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹,如果二叉樹為空則返回。
例如,下圖所示二叉樹的遍歷結果是:abdecf
2、後序遍歷首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後遍歷根結點。即:
若二叉樹為空則結束返回,
否則:(1)後序遍歷左子樹
(2)後序遍歷右子樹
(3)訪問根結點
如右圖所示二叉樹
後序遍歷結果:debfca
已知前序遍歷和中序遍歷,就能確定後序遍歷。
擴充套件資料:
圖的遍歷演算法主要有兩種,
一種是按照深度優先的順序遍歷的演算法,也就是深度優先遍歷;
另一種是按照寬度優先的順序遍歷的演算法,也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點,每次遍歷都會沿著當前節點的鄰接點遍歷,直到所有點全部遍歷完成。
如果當前節點的所有鄰接點都遍歷過了,則回溯到上一個節點,重複這一過程一直到已訪問從源節點可達的所有節點為止。
如果還存在沒有被訪問的節點,則選擇其中一個節點作為源節點並重復以上過程,直到所有節點都被訪問為止。
利用圖的深度優先搜尋可以獲得很多額外的資訊,也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點,如果所有節點均被訪問,演算法隨即終止。
寬度優先遍歷的實現一般需要一個佇列來輔助完成。
1、遍歷完所有的邊而不能有重複,即所謂「尤拉路徑問題」(又名一筆畫問題);
2、遍歷完所有的頂點而沒有重複,即所謂「哈密頓路徑問題」。
3、遍歷完所有的邊而可以有重複,即所謂「中國郵遞員問題」;
4、遍歷完所有的頂點而可以重複,即所謂「旅行推銷員問題」。
對於第一和第三類問題已經得到了完滿的解決,而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的尤拉圖的性質,而第二類問題則是研究所謂的哈密頓圖的性質。
2樓:洛雨曦
這是資料結構當中對結點進行訪問
遍歷分分先序、中序、後序
先序:先訪問根結點、左結點、右結點
中序:先訪問左結點、根結點、右結點
後序:先訪問左結點、右結點、根結點
中序:bac
後序:bca
3樓:匿名使用者
先序:根左右
後序:左右根
已知一棵二叉樹前序遍歷和中序遍歷分別為abdegcfh和dbgeachf,則該二叉樹的後序遍歷是什麼?
4樓:
已知一棵二叉樹前序遍歷和中序遍歷分別為abdegcfh和dbgeachf,則該二叉樹的後序遍歷是dgebhfca。
前序遍歷的第一個節點為根節點,由前序遍歷可知,a為根節點。中序遍歷的根節點前面的節點均為左子樹的節點,所以左子樹上的節點為dbge。去掉根節點和左子樹節點,右子數節點為chf。
前序遍歷的第二個節點為b,由2知b為左子樹節點,所以b為左子樹的根節點。
由前序遍歷,deg在b節點下面,由中序遍歷,d是b的左節點,ge是b的右節點。由前序遍歷,e是g的根節點,由中序遍歷,g是e的左子節點。由前序遍歷,c是二叉樹的右根節點,由中序遍歷,c不含左子節點,hf為c的右子節點。
由前序遍歷,f為h的根節點,由中序遍歷,h為f的左子節點。
在二叉樹中,求後序遍歷,先左後右再根,即首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。則該二叉樹的後序遍歷是dgebhfca。
5樓:後憶柏
先序遍歷的第一個結點是根結點,所以a是根,然後在中序遍歷中找到a,(dbge)a(chf),由中序遍歷的定義知(dbge)是左子樹的中序遍歷,(chf)是右子樹的中序遍歷。然後在先序遍歷中把左子樹和右子樹劃開,a(bdeg)(chf),所以b是左子樹根,c是右子樹根。然後繼續在中序遍歷中找到b和c,((d)b(ge))a(c(hf))。
對於dbeg,b是根,d是左子樹,eg是右子樹的中序遍歷,對於chf,c是根,hf是右子樹的中序遍歷。因為仍然有沒劃分完的部分,所以繼續看先序。對於bdeg,b是根已知,d是整個左子樹已知,所以eg是右子樹的先序遍歷,e是右根,再對照中序可知g是e的左子樹,chf同理。
所以樹的結構是a(b(d,e(g,)),c(,f(h,)))把它畫成圖,後序遍歷就是dgebhfca
雖然說起來很麻煩但是遞迴表達其實很簡單的..
總之先序序列是用來確定根結點,中序序列是用來劃分出左右子樹。
6樓:鞠令顓孫梓敏
後序遍歷順序:dgebhfca
7樓:保愷僑健柏
樓主您好:
你確定你寫的沒錯嗎?在檢查一次吧,我做了好長時間。感覺錯了。
8樓:不永遠是差生
我懂些資料結構,有這樣的題.你要先了解前序、中序、後序遍歷的基本性質,例如你的提問,前序中a在前、證明a是樹的根,由此再看中序遍歷a的位置,由此可知chf在a的右端其餘的在a的左端,依此類推。如果不會再發資訊給我。
祝你考試過關!
9樓:紫龍晴風
ab c
d e f h
g後序遍歷就是dgebhfca
什麼叫二叉樹前序遍歷,中序遍歷,後序遍歷?
10樓:匿名使用者
二叉樹的這三種bai
遍歷方du法,是按照每顆子樹zhi的根節點順序遍歷的。
前序dao遍歷內就是容先遍歷根節點,然後遍歷左節點,最後是右節點;
中序遍歷就是先遍歷左節點,然後遍歷中間的根節點,最後是右節點;
後序遍歷就是先遍歷左節點,然後遍歷是右節點,最後是中間的根節點。
當然要理解這些,需要了解樹的基本概念才行。
11樓:
你知不知道什麼叫做二叉樹?如果你不知道什麼是二叉樹,那麼下面的解釋對你沒有用專。
設2叉樹,根結點屬是a,葉結點左b右c
前序:a->b->c
中序:b->a->c
期待您的支援:)
二叉樹是什麼,二叉樹前序遍歷.中序遍歷.後序遍歷又是什麼
12樓:昔冉冉陶颯
你知不知道什麼叫做二叉樹?如果你不知道什麼是二叉樹,那麼下面的解釋對你沒有用。
設2叉樹,根結點是a,葉結點左b右c
前序:a->b->c
中序:b->a->c
期待您的支援:)
13樓:希一雯賁燕
樹是一種資料結構,二叉樹是樹的一種。他的結構是,根,左兒子,右兒子。。
前序,中序和後序是樹遍歷的三種不同形式
前序遍歷,也叫先根遍歷,遍歷的順序是,根,左子樹,右子樹中序遍歷,也叫中跟遍歷,順序是
左子樹,根,右子樹
後序遍歷,也叫後跟遍歷,遍歷順序,左子樹,右子樹,根
1用遞迴實現二叉樹的先序 中序 後序三種遍歷。2哈夫曼樹問題
在嗎?我給你。另外我有自己的實驗報告。裡面有遞迴遍歷,有迭代遍歷。可以寫檔案,可以壓縮編碼。可以讀檔案。你不需要什麼功能的話就刪去相應的函式就行了。希望加分。include include include include using namespace std const int maxlen 10...
楔子是什麼?和序有什麼聯絡或者區別?
長篇 的組成部分之一,但並非部長篇 所必備。通常載入 故事開始之前,起引起正文的作用。金聖嘆刪改 水滸傳 將原本的引首和第一回合併,改稱 楔子 並解釋說 楔子者,以物出物之謂也。就是以甲事引出乙事之意。下面舉個例子吧。有些朋友說看了我書的 楔子 見鬼 再看第一章,發現跟楔子一點也關係,然後就會覺得混...
什麼叫分相電流差動保護和零序電流差動保護
月似當時 分相電流差動保護是保護通過通訊通道把一端的帶有時標的電流資訊資料傳送到另一端,比較兩端的電流的大小與相位,以此判斷出是正常執行 區內故障還是區外故障。零序電流差動保護是換流變主保護,換流變壓器網側發生單相接地故障時,在換流變差動保護靈敏度不夠的情況下使用。在繞組變壓器的兩側均裝設電流互感器...