數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-資料下載頁
2025-01-18 22:24本頁面
【正文】 BiTree head。//建二叉排序樹BiTree createBST(BiTree head,int number){ BiTree p。 p=(BiTree)malloc(sizeof(BiTNode))。 pdata=number。 plchild =prchild=NULL。 if(head==NULL) { return p。 } else { if(pdata headdata) headlchild=createBST(headlchild,number)。 else headrchild=createBST(headrchild,number)。 return head。 }}//求p的雙親BiTree searchParent(BiTree head,BiTree p){ if(headlchild==p||headrchild==p||head==p||head==NULL) return head。 else { if(pdata headdata) return searchParent(headlchild ,p)。 else return searchParent(headrchild ,p)。 }}//刪除二叉排序樹中結(jié)點(diǎn)pbool Delete(BiTree p){ BiTree q,s。 q=(BiTree)malloc(sizeof(BiTNode))。 s=(BiTree)malloc(sizeof(BiTNode))。 if(!prchildamp。amp。!plchild) //刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn) { q=searchParent(head,p)。 if(qlchild==p) qlchild=NULL。 else qrchild=NULL。 } else if(!prchild){ //左子樹不為空，右子樹為空 searchParent(head,p)lchild = plchild。 free(p)。 } else if(!plchild){ //右子樹不為空，左子樹為空 searchParent(head,p)rchild = prchild。 free(p)。 } else { //左右子樹都不為空 q=p。 s=plchild。 while(srchild){ q=s。 s=srchild。 } pdata=sdata。 if(q!=p) qrchild=slchild。 else qlchild=slchild。 delete s。 } return true。}bool deleteBST(BiTree Head,int number){ if(!Head) return false。 else{ if(Headdata == number) return Delete(Head)。 else if(number Headdata) return deleteBST(Headlchild,number)。 else return deleteBST(Headrchild,number)。 }}//主程序int main(){ BiTree Head。 printf(建立一棵二叉排序樹,請(qǐng)輸入你要建樹的所有數(shù)(以1 作為結(jié)束標(biāo)志!): \n)。 Head=NULL。 int number,n。 scanf(%d,amp。number)。 while(number!=1) { Head=createBST(Head,number)。 scanf(%d,amp。number)。 } head=Head。 printf(中序遍歷二叉排序樹為： \n)。 printBST(Head)。 printf(\n)。 printf(請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn): )。 scanf(%d,amp。n)。 if(deleteBST(Head,n)) printf(刪除成功！\n)。 else printf(刪除失?。n)。 printf(刪除之后的二叉排序樹中序遍歷為：\n)。 printBST(Head)。 printf(\n)。 return 0。}3. 運(yùn)行結(jié)果 4. 實(shí)驗(yàn)體會(huì)二叉排序樹的刪除要注意分類討論，刪除的節(jié)點(diǎn)p為葉子節(jié)點(diǎn)時(shí)，不能簡(jiǎn)單的直接刪除p，而要找到p的雙親節(jié)點(diǎn)，令雙親節(jié)點(diǎn)指向p的指針為NULL即可。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1