根節(jié)點.png
在學(xué)習(xí)分治算法的時候,分治算法經(jīng)常要用到的就是遞歸了,但是嵌套遞歸讓我感覺很迷茫,在學(xué)習(xí)樹的遍歷的時候,就花了很長時間看明白樹的遍歷方式.
并且自己用棧實現(xiàn)了樹的非遞歸方式,如果讀者也對嵌套遞歸表示茫然的話,非常建議先去看一下上面的知識.
這里我要講的雖然是理解多重嵌套, 更重要的是理解分治算法,設(shè)計合適的遞歸方法來解決此類問題.
回到正題,樹的遍歷可以說是非常好的分治算法的例子了.
一顆樹,有左子樹和右子樹,
左子樹有 左子樹和右子樹
右子樹有 左子樹和右子樹
左子樹的左子樹有 左子樹和右子樹..
......
我們來看一下遞歸遍歷樹的語句
void preorderTraverse(Tree tree){
if(tree==null)return; //這是遞歸終止條件 ,遞歸終止意味返回上一級遞歸, 語句1
visit(tree); //語句2
preorderTraverse(tree.leftchild);//遞歸遍歷左子樹 語句3
preorderTraverse(tree.rightchild);//語句4
}
先來分析一下樹的前序遍歷
設(shè)當(dāng)前為(遞歸一)
- 根節(jié)點進(jìn)入
- 語句1: 根不為空 //設(shè)當(dāng)前程序為遞歸1
- 語句2:訪問根節(jié)點 [根]
- 語句3:
遞歸2:遍歷當(dāng)前樹的左子樹 ,即A
(遞歸一(遞歸二)) - A節(jié)點進(jìn)入
- 語句1: A不為空
- 語句2:訪問A [根 A]
- 語句3:
遞歸3:遍歷當(dāng)前樹的左子樹 ,即B
(遞歸一(遞歸二(遞歸三))) - B節(jié)點進(jìn)入
- 語句1: B不為空
- 語句2:訪問B節(jié)點[根 A B]
- 語句3:
遞歸4:遍歷當(dāng)前樹的左子樹 ,即D
(遞歸一(遞歸二(遞歸三(遞歸四)))) - D節(jié)點進(jìn)入
- 語句1: D不為空
- 語句2:訪問D節(jié)點 [根 A B D]
- 語句3:
遞歸5:遍歷當(dāng)前樹的左子樹 ,即E
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五))))) - E節(jié)點進(jìn)入
- 語句1: E不為空
- 語句2:訪問E節(jié)點 [根 A B D E]
- 語句3:
遞歸6:遍歷當(dāng)前樹的左子樹 ,為NULL
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五(遞歸六))))) - NULL節(jié)點進(jìn)入
- 語句1:NULL==NULL 返回 遞歸6結(jié)束 注意遞歸向上返回一級,,順序執(zhí)行下一句,
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五)))) - 此時返回到遞歸5,語句三結(jié)束, 此時執(zhí)行的是遞歸五的最后一個語句
- 執(zhí)行語句4,現(xiàn)在系統(tǒng)已經(jīng)把五的信息加載進(jìn)來了, 此時當(dāng)前樹是E
遞歸6遍歷當(dāng)前
樹的右子樹 NULL
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五{-遞歸六-}))))) - NULL節(jié)點進(jìn)入,返回 向上返回一級
- 遞歸6結(jié)束
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五))))) - 由于遞歸五執(zhí)行完畢,所以退出到 遞歸四
(遞歸一(遞歸二(遞歸三(遞歸四)))) - 當(dāng)前節(jié)點是D,語句3結(jié)束
- 語句4 :'遞歸5' 遞歸遍歷當(dāng)前節(jié)點右子樹 F 注意此時又是執(zhí)行了當(dāng)前遞歸四的最后一句
(遞歸一(遞歸二(遞歸三(遞歸四 {-遞歸五-} )))) - 語句1: F不為空
- 語句2:訪問F節(jié)點 [根 A B D E F ]
- 語句3:
遞歸6:遍歷當(dāng)前樹的左子樹 ,為NULL
(遞歸一(遞歸二(遞歸三(遞歸四{- 遞歸五(遞歸六) -} )))) - NULL節(jié)點進(jìn)入
- 語句1:NULL==NULL 返回 遞歸6結(jié)束 注意遞歸向上返回一級
(遞歸一(遞歸二(遞歸三(遞歸四(遞歸五)))))
語句四 '遞歸六' 訪問當(dāng)前節(jié)點右子樹NULL注意此時執(zhí)行開始執(zhí)行了遞歸五的最后一句
(遞歸一(遞歸二(遞歸三(遞歸四{-遞歸五{-遞歸六-} -})))) - NULL=NULL 返回 遞歸六結(jié)束,同理 遞歸五最后一句執(zhí)行完畢,遞歸四的最后一句執(zhí)行完畢 ,直接推到遞歸三
(遞歸一(遞歸二(遞歸三)))
剩下的讀者自己琢磨吧
我用{- -}區(qū)分了第二個遞歸,可以看到執(zhí)行 {- -} 遞歸后,出來直接跳到最外邊,因為{- -}內(nèi)的遞歸是最后一句
image.png
可以看到當(dāng)前是遞歸四,棧中保存了四個遞歸
點擊遞歸三,你會看他遞歸三當(dāng)前執(zhí)行的語句是淡藍(lán)色的 theFirstTraversal(root.getRightNode);也是是當(dāng)前遞歸出棧會從這里開始向下執(zhí)行.
這就是遞歸的機(jī)制,
用樹的遍歷來理解多重嵌套的遞歸,
同樣,在設(shè)計分治算法的時候,用樹了構(gòu)造自己的算法是不是容易些呢? 這也是我準(zhǔn)備做的事情.
