建站
咨詢
售后
建站咨詢
新聞中心
c語(yǔ)言編程實(shí)現(xiàn)二叉樹(shù)的三種遍歷？
二叉樹(shù)有三種遍歷方式，分別為先序遍歷、中序遍歷、后序遍歷。
專業(yè)領(lǐng)域包括成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、商城網(wǎng)站建設(shè)、微信營(yíng)銷、系統(tǒng)平臺(tái)開(kāi)發(fā)， 與其他網(wǎng)站設(shè)計(jì)及系統(tǒng)開(kāi)發(fā)公司不同，成都創(chuàng)新互聯(lián)的整合解決方案結(jié)合了幫做網(wǎng)絡(luò)品牌建設(shè)經(jīng)驗(yàn)和互聯(lián)網(wǎng)整合營(yíng)銷的理念，并將策略和執(zhí)行緊密結(jié)合，為客戶提供全網(wǎng)互聯(lián)網(wǎng)整合方案。
二叉樹(shù)是指樹(shù)中節(jié)點(diǎn)的度不大于2的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)。
知道中序和后序遍歷，畫二叉樹(shù)和寫出前序遍歷？
知道中序和后序遍歷，以中序遍歷是: HDMIBJNEAFKCG。后續(xù)遍歷是HMIDNJEBKFGCA為例，畫二叉樹(shù)和寫出前序遍歷的方法和步驟如下
1、從后序遍歷知道，最后一個(gè)必然是根節(jié)點(diǎn)，因此A是根。再結(jié)合中序遍歷可知HDMIBJNE是A的左子樹(shù)部分，F(xiàn)KCG是右子樹(shù)部分；
2、取A的右子樹(shù)部分來(lái)看先，右子樹(shù)部分的中序遍歷：FKCE，后序遍歷：KFGC。接著從后序遍歷中看A的右子樹(shù)部分KFGC，所以C是根，又從中序遍歷知，F(xiàn)K是C的左子樹(shù)部分，G是C右子樹(shù)；
3、使用同樣的方法，C的左子樹(shù)部分，中序：FK，后序：KF?？梢缘贸鯢是根，那么K只能是F的右子樹(shù)了。此時(shí)如圖所示，A的右子樹(shù)部分都出來(lái)了；
4、再看，A的左子樹(shù)部分HDMIBJE，中序：HDMIBJNE，后序：HMIDNJEB。后序遍歷可知，B是根結(jié)點(diǎn)，那么再結(jié)合中序遍歷可知道HDMI是B的左子樹(shù)部分，JNE是B的右子樹(shù)部分；
5、緊接著就是看B的左子樹(shù)部分HDMI，中序：HDMI，后序：HMID，可知D是根，H是D的左子樹(shù)，MI是D的右子樹(shù)部分；
6、看到D的右子樹(shù)部分，中序后序都是MI，根據(jù)后序中序的特性可知道，根只能是I，M是I的左子樹(shù)；
7、再接著看看B的右子樹(shù)部分JNE，中序：JNE，后序：NJE，后序看出E是根，中序看出E無(wú)右子樹(shù)，只有JN是E的左子樹(shù)部分；
8、最后看JN的中序：JN，后序：NJ，根據(jù)后序特性看出，J是根，中序看出N是J的右子樹(shù)，那么整體的二叉樹(shù)就出來(lái)了。
中序遍歷規(guī)則？
中序遍歷的過(guò)程可以看作是一棵樹(shù)的“掃描”，其過(guò)程規(guī)則如下：
1.先從樹(shù)的根節(jié)點(diǎn)開(kāi)始遍歷
2.接著沿著樹(shù)的左子樹(shù)，依次訪問(wèn)每個(gè)節(jié)點(diǎn)，直到訪問(wèn)到最左側(cè)葉子節(jié)點(diǎn)。
3.然后，訪問(wèn)根節(jié)點(diǎn)。
4.再接著，沿著右子樹(shù)，依次訪問(wèn)每個(gè)節(jié)點(diǎn)，直到訪問(wèn)到最右側(cè)葉子節(jié)點(diǎn)
5.最后，重復(fù)上述過(guò)程，直至遍歷完樹(shù)中所有的節(jié)點(diǎn)。
中序遍歷是一種二叉樹(shù)的遍歷方式，其基本步驟是：
1. 從根節(jié)點(diǎn)開(kāi)始，沿著左子樹(shù)方向前進(jìn)，直至遇到一個(gè)葉子節(jié)點(diǎn)，訪問(wèn)該節(jié)點(diǎn)；
2. 如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹(shù)，則向上回溯，直至某個(gè)節(jié)點(diǎn)有右子樹(shù)，訪問(wèn)該節(jié)點(diǎn)；
3. 從步驟1開(kāi)始，重復(fù)沿著右子樹(shù)方向前進(jìn)，直至葉子節(jié)點(diǎn)。
樹(shù)的遍歷順序大體分為三種：前序遍歷（先根遍歷、先序遍歷），中序遍歷（中根遍歷），后序遍歷（后根遍歷）。
規(guī)則
前序遍歷的規(guī)則：
（1）訪問(wèn)根節(jié)點(diǎn)
（2）前序遍歷左子樹(shù)
（3）前序遍歷右子樹(shù)
中序遍歷的規(guī)則：
一棵二叉樹(shù)的先序遍歷？
1、先序遍歷第一個(gè)為樹(shù)的根，先序遍歷是先根再左子樹(shù)最后右子樹(shù)，第一個(gè)肯定是樹(shù)的根，先畫A，A再中序遍歷中左右都有，說(shuō)明A有左子樹(shù)也有右子樹(shù)。
2、然后看先序第一個(gè)值是B，在中序中為A的前面，所以B是A的左子樹(shù)
3、繼續(xù)看先序，接下來(lái)是C、D，C再中序中再B的前面，所以C是B的左子樹(shù)，D在B后面，D是B的
4、接下來(lái)是E，E在中序是在D后面A前面，所以E是D的右子樹(shù)
5、接著先序中是F，F(xiàn)在中序?yàn)锳后面，是A的右子樹(shù)
到此，以上就是小編對(duì)于java二叉樹(shù)的遍歷算法代碼的問(wèn)題就介紹到這了，希望這4點(diǎn)解答對(duì)大家有用。
名稱欄目：Java二叉樹(shù)的遍歷方式有哪些
文章轉(zhuǎn)載：http://www.dlmjj.cn/article/ccoespg.html
