【正文】 //=====================中序線索化 ========================== void inThread(Btree p) //線索化 { if(p) { inThread(plchild)。 //左子樹線索化 if(plchild==NULL) //前驅(qū)線索 { plchild=pre。 //建立當(dāng)前節(jié)點(diǎn)的前驅(qū)線索 pltag=1。 } else pltag=0。 if(prerchild==NULL) //后繼線索 { prerchild=p。 prertag=1。 } else prertag=0。 pre=p。 inThread(prchild)。 //右子樹線索化 } } Btree InOrderThread(Btree t) //中序線索化二叉樹 { Btree root。 root=(Btree)malloc(sizeof(Bnode))。//創(chuàng)建根節(jié)點(diǎn) 25 / 30 rootltag=0。 rootrtag=1。 rootrchild=t。 if(t==NULL) rootlchildroot。 else { rootlchild=t。 pre=root。 //pre 是 p 的前驅(qū)節(jié)點(diǎn) inThread(t)。 // 中序遍歷線索化二叉樹 prerchild=root。 prertag=1。 rootrchild=pre。 //根節(jié)點(diǎn)右線索化 } return root。 } void inOrder(Btree t) //中序線索遍歷 { Btree p=tlchild。 while(p!=t) { while(pltag==0) p=plchild。 printf(%c,pdata)。 while(prtag==1amp。amp。prchild!=t) { p=prchild。 printf(%c,pdata)。 } p=prchild。 } } void Binary_Tree_pre() { Btree t。 printf(\t 先序輸入二叉樹 (表示空節(jié)點(diǎn) ):\n\t )。 t=CreateBtree1()。 //先序遍歷創(chuàng)建二叉樹 printf(\t 顯示二叉樹信息： \n)。 printf(\t 先序遍歷 (遞歸 ):)。 PreOrder1(t)。 26 / 30 printf(\n)。 printf(\t 先序遍歷 (非遞歸 ):)。 PreOrder2(t)。 printf(\n)。 printf(\t 中序遍歷 (遞歸 ):)。 InOrder1(t)。 printf(\n)。 printf(\t 中序遍歷 (非遞歸 ):)。 InOrder2(t)。 printf(\n)。 printf(\t 后序遍歷 (遞歸 ):)。 PostOrder1(t)。 printf(\n)。 printf(\t 后序遍歷 (非遞歸 ):)。 PostOrder2(t)。 printf(\n)。 printf(\t 按層次遍歷二叉樹 :)。 LevelOrder(t)。 printf(\n)。 printf(\t 二叉樹葉子數(shù)為 :%d,leaf(t))。 printf(\n)。 printf(\t 二叉樹深度為 :%d,Depth(t))。 printf(\n)。 printf(\t 二叉樹總結(jié)點(diǎn)數(shù)計(jì)算 :%d,count_tree(t))。 printf(\n)。 Btree tb。 tb=InOrderThread(t)。 printf(\t 線索中序遍歷： )。 inOrder(tb)。 printf(\n)。 menu()。 } void Binary_Tree_level() 27 / 30 { Btree t。 printf(\t 層次輸入二叉樹 (表示空節(jié)點(diǎn) ):\n\t )。 t= create_level_Btree2()。 //層次遍歷二叉樹創(chuàng)建 printf(\t 顯示二叉樹信息： \n)。 printf(\t 先序遍歷 (遞歸 ):)。 PreOrder1(t)。 printf(\n)。 printf(\t 先序遍歷 (非遞歸 ):)。 PreOrder2(t)。 printf(\n)。 printf(\t 中序遍歷 (遞歸 ):)。 InOrder1(t)。 printf(\n)。 printf(\t 中序遍歷 (非遞歸 ):)。 InOrder2(t)。 printf(\n)。 printf(\t 后序遍歷 (遞歸 ):)。 PostOrder1(t)。 printf(\n)。 printf(\t 后序遍歷 (非遞歸 ):)。 PostOrder2(t)。 printf(\n)。 printf(\t 按層次遍歷二叉樹 :)。 LevelOrder(t)。 printf(\n)。 printf(\t 二叉樹葉子數(shù)為 :%d,leaf(t))。 printf(\n)。 printf(\t 二叉樹深度為 :%d,Depth(t))。 printf(\n)。 printf(\t 二叉樹總結(jié)點(diǎn)數(shù)計(jì)算 :%d,count_tree(t))。 printf(\n)。 28 / 30 Btree tb。 tb=InOrderThread(t)。 printf(\t 線索中序遍歷： )。 inOrder(tb)。 printf(\n)。 menu()。 } void menu() //菜單 { printf(\n\t+二叉樹一般操作 +\n)。 printf(\t+ 先序創(chuàng)建二叉樹 +\n)。 printf(\t+ 層次創(chuàng)建二叉樹 +\n)。 printf(\t+ 退出程序 +\n)。 printf(\t+ (請(qǐng)正確輸入數(shù)據(jù) ) +\n)。 int item。 printf(\t 輸入菜單選項(xiàng)： )。 scanf(%d,amp。item)。 switch(item) { case 1:getchar()。Binary_Tree_pre()。 case 2:getchar()。Binary_Tree_level()。 。 case 3:printf(\t***退出程序成功 \n)。exit(0)。break。 default:printf(\n\t ***(請(qǐng)?jiān)?13 中選擇 )***)。printf(\n)。menu()。break。 } } int main() { menu()。 /* 先序遍歷創(chuàng)建二叉樹輸入 :abdgcefh 層次遍歷二叉樹創(chuàng)建輸入 :abcdefgh */ } 五、運(yùn)行截圖 先序遍歷創(chuàng)建二叉樹 29 / 30 層次遍歷創(chuàng)建二叉樹 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié) 30 / 30 本次課程設(shè)計(jì)，使我對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程有了更深入的理解?！稊?shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性較強(qiáng)的課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。 剛開(kāi)始做課程設(shè)計(jì)的時(shí)候，感到完全無(wú)從下手，甚至讓我覺(jué)得完成這次程序設(shè)計(jì)根本就是不可能的，于是開(kāi)始查閱各種資料以及參考文獻(xiàn)，之后便開(kāi)始著手寫程序，寫完運(yùn)行時(shí)有很多問(wèn)題。特別是實(shí)現(xiàn)線索二叉樹時(shí)沒(méi)有考慮周全，經(jīng)常運(yùn)行出現(xiàn)錯(cuò)誤，但通過(guò)同學(xué)間的幫助最終基本解決問(wèn)題。通過(guò)這段時(shí)間的課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時(shí)間上機(jī)練習(xí)。這次的程序訓(xùn)練培養(yǎng)了 我實(shí)際分析問(wèn)題、編程和動(dòng)手能力，使我掌握了程序設(shè)計(jì)的基本技能，提高了我適應(yīng)實(shí)際，實(shí)踐編程的能力。 雖然課程設(shè)計(jì)做的不夠完善，但在設(shè)計(jì)的過(guò)程中受益匪淺，通過(guò)查資料等學(xué)到了很多以前不知道或不太會(huì)應(yīng)用的知識(shí)，對(duì)單向鏈表的使用有了更深刻的了解和掌握，因?yàn)槎囗?xiàng)式的計(jì)算要求用單向鏈表來(lái)實(shí)現(xiàn)，所以在做課程設(shè)計(jì)之前通過(guò)網(wǎng)上找資料，查參考書等，使我對(duì)單向鏈表的使用比以前掌握的更加到位，并且能夠靈活運(yùn)用，通篇幾乎用的都是單向鏈表，這是受益的一大重點(diǎn)。 這次課程設(shè)計(jì)，對(duì)我的程序設(shè)計(jì)和調(diào)試能力有很大的提升。這次課程設(shè)計(jì) 使我深刻認(rèn)識(shí)到自己專業(yè)知識(shí)的匱乏，程序設(shè)計(jì)的能力的不足。通過(guò)這次的課程設(shè)計(jì)也提高了我的獨(dú)立思考、敢于實(shí)踐操作能力，彌補(bǔ)了我的部分專業(yè)知識(shí)的不足之處。我的程序設(shè)計(jì)思想和代碼的編寫和調(diào)試能力在此次課程設(shè)計(jì)期間有所提高。這樣一種更貼切實(shí)際的課程設(shè)計(jì)，更能提高我的學(xué)習(xí)效率，讓我真正理解這門課程的知識(shí)要點(diǎn)。