程序二叉樹的遍歷及其應(yīng)用-免費(fèi)閱讀
【正文】 5總結(jié)語二叉樹在計(jì)算機(jī)科學(xué)中有著重要的作用, 現(xiàn)實(shí)世界中有好多問題都是用樹這種數(shù)據(jù)結(jié)構(gòu)描述的, 而二叉樹在計(jì)算機(jī)中操作和實(shí)現(xiàn)都非常方便。由 a、b、c可知對于任意個(gè)結(jié)點(diǎn)的二叉樹都可由先序遍歷序列和中序遍歷序列唯一確定[4]。規(guī)律2: 前序序列遍歷最后一個(gè)為根結(jié)點(diǎn)右子樹的最右葉子結(jié)點(diǎn), 中序遍歷的最后一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)右子樹的最右葉子結(jié)點(diǎn)。①根據(jù)先序序列知道B為根節(jié)點(diǎn)。 postorder()。編程時(shí)，可以用如下代碼： public void inorder(Node ptr){ if (ROOT==null) { (Tree is empty)。而對于以B、C 為根結(jié)點(diǎn)的兩個(gè)子樹，還可繼續(xù)將其拆分為左、右子樹，按左中右的順序，遍歷左子樹直到其只有一個(gè)結(jié)點(diǎn)或?yàn)榭諡橹?，然后遍歷右子樹，直到其右子樹只有一個(gè)結(jié)點(diǎn)或?yàn)榭諡橹筟3]。遞歸算法具有簡練、清晰等優(yōu)點(diǎn)，但因其執(zhí)行過程涉及到大量的堆棧使用，難于應(yīng)用到一些嚴(yán)格限制堆棧使用的系統(tǒng)，也無法應(yīng)用到一些不支持遞歸的語言環(huán)境[9]。inorder traversal。優(yōu)集學(xué)院學(xué)期論文二叉樹的遍歷及其應(yīng)用摘要：二叉樹是一種特殊的樹，它在計(jì)算機(jī)科學(xué)領(lǐng)域提供了大量的實(shí)際應(yīng)用。 preorder traversal。1遍歷二叉樹的概念所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問一次。此步驟可借助圖1 來講解。 return。 ( + )。②從中序序列得出F、E為以B為根節(jié)點(diǎn)的左子樹上節(jié)點(diǎn)，B右邊的節(jié)點(diǎn)G、C、H、D即為以B為根節(jié)點(diǎn)的右子樹上節(jié)點(diǎn)。規(guī)律3: 中序序列遍歷第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)左子樹的最左葉子結(jié)點(diǎn), 后序遍歷的第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)左子樹的最左葉子結(jié)點(diǎn)。（2）先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。二叉樹在計(jì)算機(jī)領(lǐng)域應(yīng)用很廣泛，二叉樹的遍歷又是最基礎(chǔ)的操作，所以對二叉樹遍歷方法的研究就更為重要。 對于二叉樹（2）, 它的中序遍歷序列也是: ABC , 這顯然不是同一棵二叉樹但它們卻有相同的中序遍歷序列。在中序遍列序列中根結(jié)點(diǎn)前面的結(jié)點(diǎn)序列就是根結(jié)點(diǎn)左子樹的中序遍歷序列, 在先序遍歷序列中根結(jié)點(diǎn)后面的屬于中序遍歷序列中根結(jié)點(diǎn)前面的那些結(jié)點(diǎn)組成序列就是根結(jié)點(diǎn)左子樹的先序遍歷序列, 因?yàn)楦Y(jié)點(diǎn)的左子樹至少比原二叉樹少一
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1