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

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

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

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