【正文】 二 叉 樹(shù) 如 下:n”)。print_btree(root,0)。printf(“”)。printf(“”)。printf(“★★★★★★★★★請(qǐng)輸入您想要執(zhí)行的操作!:★★★★★★★★★”)。printf(“”)。printf(“選擇1—————————————進(jìn)行先序遍歷”)。printf(“”)。軟件課程設(shè)計(jì)2010年1月printf(“選擇2—————————————進(jìn)行中序遍歷”)。printf(“”)。printf(“選擇3—————————————進(jìn)行后序遍歷”)。printf(“”)。printf(“選擇4—————————————進(jìn)行查詢結(jié)點(diǎn)”)。printf(“”)。printf(“選擇5—————————————進(jìn)行退出操作”)。printf(“”)。printf(“★★★★★★★★★溫馨提示:請(qǐng)選擇數(shù)字鍵0～5 ★★★★★★★★★”)。printf(“”)。printf(“”)。while(1){scanf(“%d”,amp。n)。switch(n){case 1:printf(“ 先 序 遍 歷 為:n”)。PreorderTraversal(root)。printf(“nn”)。break。case 2:printf(“ 中 序 遍 歷 為:n”)。InorderTraversal(root)。printf(“nn”)。break。case 3:printf(“ 后 序 遍 歷 為:n”)。PostorderTraversal(root)。printf(“nn”)。break。case 4:光信0804廖娟U200813197printf(“ 請(qǐng) 輸 入 您 要 查 詢 的 結(jié) 點(diǎn):n”)。scanf(“%s”,amp。c)。printf(“ 您 要 查 詢 的 結(jié) 點(diǎn) 為:n”)。root=search_btree(root,c)。printf(“n”)。break。case 5:printf(“光 信 0 8 0 4 ———— 廖 娟nn”)。printf(“0 1 0 年 1 月nn”)。return。default:printf(“ 您 的 輸 入 有 誤，請(qǐng) 重 新 輸 入！!n”)。break。}} } /* 結(jié)束*//* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ struct tree *create_btree(struct tree *root,struct tree *r,char info)/* struct tree *root:根結(jié)點(diǎn)struct tree *r:要增加的結(jié)點(diǎn)char info:要保存的數(shù)據(jù)*/ {if(r==0)// 如果當(dāng)前位置無(wú)結(jié)點(diǎn)，則將新結(jié)點(diǎn)插入此處{r=new(struct tree)。// same as function: malloc(sizeof())if(r == 0){printf(“ Out of memoryn”)。return 0。}rleft= 0。rright=0。rinfo=info。// root為空，則插入后保存至根結(jié)點(diǎn)處if(root)// 如果二叉樹(shù)存在,則將新建結(jié)點(diǎn)與二叉樹(shù)連接起來(lái)軟件課程設(shè)計(jì)2010年1月{if(infoinfo)root left=r。elseroot right=r。// 按左結(jié)點(diǎn)}else// 如果根結(jié)點(diǎn)不存在，即二叉樹(shù)不存在，則將新建一個(gè)二叉樹(shù){rright=0。rleft=0。}return r。}/* if = = 0 接下頁(yè)*//* 判斷要插入的節(jié)點(diǎn)應(yīng)該在當(dāng)前節(jié)點(diǎn)的左子樹(shù)或右子樹(shù)，遞歸插入*/ if(info rinfo)create_btree(r,rleft,info)。if(info=rinfo)create_btree(r,rright,info)。}/* *create_btree(root,r,info)*//* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 查詢數(shù)據(jù)*/ struct tree *search_btree(struct tree *root,char key)/* struct tree *root:要查詢的二叉樹(shù)首地址char key:要查詢的數(shù)據(jù)*/ {tree *t。t=root。if(!t)// 如果二叉樹(shù)指針為空，輸出Empty btree {printf(“ Empty btree！!n”)。return root。}while(tinfo!=key){if(keyinfo)// 按照“左結(jié)點(diǎn)t=tleft。elset=tright。if(t==0)// 如果指針為空，則退出查找光信0804廖娟U200813197{printf(“ Search Failure！!n”)。break。} } /* while(rootinfo!=key)*/ if(t!=0)// 如果二叉樹(shù)指針不為空，即查找成功給出信息，返回printf(“ Successful search！!n key=%”,tinfo)。return root。} /* *search_btree(root,key)*//* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 打印二叉樹(shù)*/ void print_btree(struct tree *r,int l)/* struct tree *r:二叉樹(shù)首地址int l:當(dāng)前結(jié)點(diǎn)的高度，根結(jié)點(diǎn)為0輸出的二叉樹(shù)為正常樹(shù)逆旋轉(zhuǎn)90176。后成鏡像的結(jié)果*/ {int i。if(r == 0)return。//如果傳入指針為0，則返回print_btree(rleft,l+1)。//打印左結(jié)點(diǎn)for(i=0。iprintf(“ ”)。//打印空格，用來(lái)排版控制格式printf(“%”,rinfo)。//打印根結(jié)點(diǎn)print_btree(rright,l+1)。//打印右結(jié)點(diǎn) } /**print_btree(root,0)*//* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 先序遍歷*/ void PreorderTraversal(struct tree *root){ if(root==0)return。printf(“%c”,rootinfo)。PreorderTraversal(rootleft)。PreorderTraversal(rootright)。}軟件課程設(shè)計(jì)2010年1月/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 中序遍歷*/ void InorderTraversal(struct tree *root){ if(!root)return。InorderTraversal(rootleft)。printf(“%c”,rootinfo)。InorderTraversal(rootright)。}/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 后序遍歷*/ void PostorderTraversal(struct tree *root){ if(!root)return。PostorderTraversal(rootleft)。PostorderTraversal(rootright)。printf(“%c”,rootinfo)。}參考文獻(xiàn)《數(shù)據(jù)結(jié)構(gòu)》（c語(yǔ)言版）嚴(yán)蔚敏吳偉民 編著 清華大學(xué)出版社 《C語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 編著 清華大學(xué)出版社 《C程序上機(jī)指導(dǎo)》 譚浩強(qiáng) 編著 清華大學(xué)出版社《標(biāo)準(zhǔn)c語(yǔ)言程序設(shè)計(jì)及應(yīng)用》 周純杰 編著 華中科技大學(xué)出版社