設(shè)二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),試設(shè)計(jì)一個(gè)算法計(jì)算一棵給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目

1、設(shè)二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),試設(shè)計(jì)一個(gè)算法計(jì)算一棵給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目include include define max 10 typedef struct node char data node lchildrchild Bitree Bitree Bmax Bitree Creatree /建立二叉樹 Bitree TS char ch int frontrearsign sign0 front0 rear-1 TNULL printf 建立二叉樹:n chgetchar whilech ifch /輸入結(jié)點(diǎn)不是虛結(jié)點(diǎn)SBitree mallocsizeofBitree S-data

2、ch S-lchildS-rchildNULL rear BrearS ifrearfront TS sign else ifsign21 /尋找父結(jié)點(diǎn) Bfront-lchildS ifsign20 Bfront-rchildS front sign else /輸入結(jié)點(diǎn)為虛結(jié)點(diǎn) ifsign20 front sign chgetchar return T int SearchleafBitree T /計(jì)算葉子數(shù) ifTNULL return 0 else ifT-lchildNULLT-rchildNULL return 1 else returnSearchleafT-lchildSe

3、archleafT-rchild void visitBitree T printfcnT-data void InorderBitree T / 中序遍歷二叉樹 ifTNULL InorderT-lchild visitT InorderT-rchild void main Bitree T TCreatree printf 中序遍歷 :n InorderT printf 葉子數(shù) dnSearchleafT 題目 設(shè)二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)試設(shè)計(jì)一 個(gè)算法計(jì)算一棵給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目。問題分析本程序要求在一棵二叉樹中實(shí)現(xiàn)計(jì)算葉子結(jié)點(diǎn)數(shù)目的功能為完成上述功能需要解決的關(guān)鍵問題是建立二叉樹過

4、程及查找葉子結(jié)點(diǎn)過程。概要設(shè)計(jì)建立一個(gè)以二叉鏈表方式存儲(chǔ)的二叉樹輸入結(jié)點(diǎn)信息時(shí)按照完全二叉樹的結(jié)點(diǎn)順序輸入。 先序遍歷二叉樹并判斷遍歷的根是否是葉子結(jié)點(diǎn)若是并記錄葉子結(jié)點(diǎn)個(gè)數(shù)。葉子結(jié)點(diǎn)判斷條件為左孩子域和右孩子域都為空。詳細(xì)設(shè)計(jì)建立二叉樹時(shí)按照完全二叉樹的結(jié)點(diǎn)順序輸入表示虛結(jié)點(diǎn)表示輸入結(jié)束。 若不是虛結(jié)點(diǎn)時(shí)則建立一個(gè)新結(jié)點(diǎn)并且將其作為左孩子或右孩子結(jié)點(diǎn)連接到它的父結(jié)點(diǎn)上第一個(gè)結(jié)點(diǎn)無父結(jié)點(diǎn)若是虛結(jié)點(diǎn)則將空結(jié)點(diǎn)NULL作為左孩子或右孩子結(jié)點(diǎn)連接到它的父節(jié)點(diǎn)上。查找葉子結(jié)點(diǎn)利用遞歸先序遍歷二叉樹方法來查找葉子結(jié)點(diǎn)當(dāng)遍歷一個(gè)根結(jié)點(diǎn)時(shí)判斷其左孩子域和右孩子域是否都為空若都為空則該結(jié)點(diǎn)是葉子結(jié)點(diǎn)并用記錄葉子個(gè)數(shù)否則不是葉子結(jié)點(diǎn)。調(diào)試分析及小結(jié)錯(cuò)誤及分析當(dāng)按照完全二叉樹的結(jié)點(diǎn)順序輸入ABCDE 后程序無法運(yùn)行。經(jīng)測試發(fā)現(xiàn)在建立二叉樹時(shí)出現(xiàn)問題。當(dāng)掃描到 B 時(shí)執(zhí)行 else ifsign21 Bfront-lchildS Signifsign20 Bfront-rchildS front sign注執(zhí)行上述程序前sign1Bfront 指向關(guān)鍵字為 A 的結(jié)點(diǎn)。 當(dāng)一個(gè) if 語句段執(zhí)行完后關(guān)鍵字為 A 的結(jié)點(diǎn)的左孩子為關(guān)鍵字為 B 的結(jié)點(diǎn) sign2。此時(shí)本應(yīng)結(jié)束 else 語句段但由于 sign2 則第二個(gè) if 語句條件為真繼續(xù)執(zhí)行因此導(dǎo)致程序執(zhí)行出錯(cuò)。 改正在 if 語