設二叉樹采用鏈式存儲結(jié)構(gòu)試設計一個算法計算一棵給定二叉樹中葉子結(jié)點的數(shù)目

1、設二叉樹采納鏈式儲存構(gòu)造,試設計一個算法計算一棵給定二叉樹中葉子結(jié)點的數(shù)量includeincludedefinemax10typedefstructnodechardatanodelchildrchildBitreeBitreeBmaxBitreeCreatree/成立二叉樹BitreeTScharchintfrontrearsignsign0front0rear-1TNULLprintf成立二叉樹:nchgetcharwhilechifch/輸入結(jié)點不是虛結(jié)點SBitreemallocsizeofBitreeS-datachS-lchildS-rchildNULLrearBrearSifr

2、earfrontTSsignelseifsign21/找尋父結(jié)點Bfront-lchildSifsign20Bfront-rchildSfrontsignelse/輸入結(jié)點為虛結(jié)點ifsign20frontsignchgetcharreturnTintSearchleafBitreeT/計算葉子數(shù)ifTNULLreturn0elseifT-lchildNULLT-rchildNULLreturn1elsereturnSearchleafT-lchildSearchleafT-rchildvoidvisitBitreeTprintfcnT-datavoidInorderBitreeT/中序遍歷二

3、叉樹ifTNULLInorderT-lchildvisitTInorderT-rchildvoidmainBitreeTTCreatreeprintf中序遍歷:nInorderTprintf葉子數(shù)dnSearchleafT題目設二叉樹采納鏈式儲存構(gòu)造試設計一個算法計算一棵給定二叉樹中葉子結(jié)點的數(shù)量。問題剖析本程序要求在一棵二叉樹中實現(xiàn)計算葉子結(jié)點數(shù)量的功能為達成上述功能需要解決的重點問題是成立二叉樹過程及查找葉子結(jié)點過程。綱要設計成立一個以二叉鏈表方式儲存的二叉樹輸入結(jié)點信息時依據(jù)完整二叉樹的結(jié)點次序輸入。先序遍歷二叉樹并判斷遍歷的根能否是葉子結(jié)點假如并記錄葉子結(jié)點個數(shù)。葉子結(jié)點判斷條件為左孩

4、子域和右孩子域都為空。詳盡設計建立二叉樹時依據(jù)完整二叉樹的結(jié)點次序輸入表示虛結(jié)點表示輸入結(jié)束。若不是虛結(jié)點時則成立一個新結(jié)點而且將其作為左孩子或右孩子結(jié)點連結(jié)到它的父結(jié)點上第一個結(jié)點無父結(jié)點假如虛結(jié)點則將空結(jié)點NULL作為左孩子或右孩子結(jié)點連結(jié)到它的父節(jié)點上。查找葉子結(jié)點利用遞歸先序遍歷二叉樹方法來查找葉子結(jié)點當遍歷一個根結(jié)點時判斷其左孩子域和右孩子域能否都為空若都為空則該結(jié)點是葉子結(jié)點并用記錄葉子個數(shù)不然不是葉子結(jié)點。調(diào)試剖析及小結(jié)錯誤及剖析當依據(jù)完整二叉樹的結(jié)點次序輸入ABCDE后程序沒法運轉(zhuǎn)。經(jīng)測試發(fā)此刻成立二叉樹時出現(xiàn)問題。當掃描到B時履行elseifsign21Bfront-lchildSSignifsign20Bfront-rchildSfrontsign注履行上述程序前sign1Bfront指向重點字為A的結(jié)點。當一個if語句段履行完后重點字為A的結(jié)點的左孩子為重點字為B的結(jié)點sign2。此時本應結(jié)束else語句段但因為sign2則第二個if語句條件為真持續(xù)履行所以致使程序履行犯錯。更正在if語