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

1、設二叉樹采用鏈式存儲結(jié)構(gòu),試設計一個算法計算一棵給定二叉樹中葉子結(jié)點的數(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é)點不是虛結(jié)點SBitree mallocsizeofBitree S-data

2、ch S-lchildS-rchildNULL rear BrearS ifrearfront TS sign else ifsign21 /尋找父結(jié)點 Bfront-lchildS ifsign20 Bfront-rchildS front sign else /輸入結(jié)點為虛結(jié)點 ifsign20 front sign chgetchar return T int SearchleafBitree T /計算葉子數(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 題目 設二叉樹采用鏈式存儲結(jié)構(gòu)試設計一 個算法計算一棵給定二叉樹中葉子結(jié)點的數(shù)目。問題分析本程序要求在一棵二叉樹中實現(xiàn)計算葉子結(jié)點數(shù)目的功能為完成上述功能需要解決的關鍵問題是建立二叉樹過

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