|
本來(lái)只是一個(gè)復(fù)習(xí)的，但是為了能系統(tǒng)的理解性復(fù)習(xí)所以在此花了一段時(shí)間來(lái)寫這個(gè)博文,，同時(shí)為了貢獻(xiàn)自己的知識(shí),，讓那些初學(xué)者徹底理解遞歸調(diào)用，寫了寫自我的理解,。一直受那句的影響：只有對(duì)一個(gè)知識(shí)和技術(shù)有足夠的理解后,，才能寫出簡(jiǎn)單易懂的教程。 1.二叉樹的實(shí)現(xiàn) 二叉樹的插入：首先給一個(gè)初始節(jié)點(diǎn),，接下來(lái)：如果插入的節(jié)點(diǎn)比這個(gè)節(jié)點(diǎn)大,，插入到樹的左邊，否則插入到樹的右邊,，這是在左右節(jié)點(diǎn)為空的情況下,。但是此時(shí)我們?nèi)绻筮呌泄?jié)點(diǎn)怎么辦，此時(shí)如果我們?cè)贗nsert函數(shù)中再次調(diào)用Insert函數(shù)時(shí),，系統(tǒng)會(huì)執(zhí)行進(jìn)棧操作,，系統(tǒng)會(huì)把當(dāng)前的節(jié)點(diǎn)壓入棧中，調(diào)用左孩子或者右孩子的Insert函數(shù),，所以如果一直有左孩子,，會(huì)一直執(zhí)行進(jìn)棧操作直到?jīng)]有判斷的這個(gè)節(jié)點(diǎn)沒(méi)有左孩子為止，這樣就新建一個(gè)節(jié)點(diǎn)賦給這個(gè)節(jié)點(diǎn)的左孩子,。二叉樹的遍歷：同插入類似：由于在主函數(shù)中初始的那個(gè)值作為根節(jié)點(diǎn)（那個(gè)t,，它的值就是1），在遍歷的時(shí)候首先判斷它有沒(méi)有左孩子,，如果有左孩子就一直執(zhí)行進(jìn)棧操作,，這樣節(jié)點(diǎn)的打印操作都無(wú)法執(zhí)行,，但是一旦發(fā)現(xiàn)節(jié)點(diǎn)沒(méi)有左孩子，就先執(zhí)行一個(gè)打印操作,，這樣輸出的樹中最左邊孩子節(jié)點(diǎn)的值,，接著判斷有沒(méi)有右孩子如果有，就再次執(zhí)行進(jìn)棧操作,，這樣如果既沒(méi)有左孩子右沒(méi)有了右孩子就執(zhí)行退棧操作。同時(shí)為了能使節(jié)點(diǎn)數(shù)據(jù)能用于比計(jì)較（可以想象成節(jié)點(diǎn)泛型數(shù)據(jù)是數(shù)值型數(shù)據(jù)集合）需要使數(shù)據(jù)類型繼承IComparable接口（其實(shí)數(shù)值型數(shù)據(jù)能直接比較大小就是繼承了這個(gè)接口）,。
2.二叉樹遍歷的理解 如果對(duì)于上述遍歷仍然不清楚可以看看下面對(duì)于二叉樹的遍歷理解 要想徹底的理解遞歸就必須對(duì)程序調(diào)用子程序的過(guò)程有所了解,，也就是系統(tǒng)對(duì)程序點(diǎn)的壓棧和出棧操作，在主程序調(diào)用子程序的時(shí)候,，系統(tǒng)是將子程序的入口點(diǎn)做壓棧操作,，在調(diào)用完子程序后，系統(tǒng)執(zhí)行退棧操作,，繼續(xù)從主程序的位置往下執(zhí)行,。如果子程序中還有子程序，就會(huì)多次執(zhí)行壓棧和退棧操作,。如圖左邊是二叉樹,，右邊是遍歷代碼。 首先判斷根節(jié)點(diǎn)A的左子樹是否為空,，因?yàn)锳有左子樹所以執(zhí)行代碼1,，這是相當(dāng)于執(zhí)行子程序了，系統(tǒng)為了保證程序能正常執(zhí)行,，需要現(xiàn)將1位置處的斷點(diǎn)壓棧,，為的就是在執(zhí)行完子程序后能讓主程序繼續(xù)執(zhí)行，所以：我們可以想象系統(tǒng)在執(zhí)行節(jié)點(diǎn)A時(shí)將代碼1位置的斷點(diǎn)壓棧（我們?cè)谶@里為了簡(jiǎn)單就說(shuō)將A壓棧）,，接著執(zhí)行節(jié)點(diǎn)A的左子樹B的遍歷,，由于節(jié)點(diǎn)B還是有左子樹，所以繼續(xù)將B壓棧,，由于D沒(méi)有左子樹,，所以執(zhí)行D層中的打印語(yǔ)句（也就是代碼2），接著判斷D有沒(méi)有右子樹,，發(fā)現(xiàn)D沒(méi)有右子樹,，于是系統(tǒng)開始出棧操作，這時(shí)的棧中有那些斷點(diǎn)呢 棧：A BB出棧,，斷點(diǎn)出棧后,，程序是從斷點(diǎn)的下一條指令開始執(zhí)行，因?yàn)閕f語(yǔ)句中沒(méi)有指令了,，于是就從2開始執(zhí)行,，調(diào)用打印B的操作，接著由于B有右子樹，所以開始執(zhí)行3,，此時(shí)再次將B層的這個(gè)斷點(diǎn)壓棧,，去執(zhí)行E層的代碼，由于E沒(méi)有左子樹所以執(zhí)行打印E的操作,，同時(shí)E沒(méi)有右孩子,，所以退棧到B層，但是B層的下一條指令沒(méi)有了,，于是B層執(zhí)行完了跳出B層回到A層,，此時(shí)棧中保存的是A層的1處的斷點(diǎn)，所以繼續(xù)上面的思路執(zhí)行A層的代碼2打印A,，接著由于A有右孩子,，于是C進(jìn)棧，和前面的思路一樣,，打印完F,，退回到C層打印C，最后打印G,，在G層執(zhí)行完后退回到C層3處,，同樣C層沒(méi)有可執(zhí)行的代碼跳出C層，繼續(xù)退回到A層3出,，A層3處的下一條指令也沒(méi)有了,，于是A層執(zhí)行完跳出，至此棧中也空程序執(zhí)行完畢,。 |
|
|
