軟件基礎(chǔ)實(shí)驗(yàn)報(bào)告之二叉樹(shù)

軟件基礎(chǔ)上機(jī)題之二叉樹(shù)PAGEPAGE3

年級(jí)10級(jí)班號(hào)5

學(xué)號(hào)

10064132專(zhuān)業(yè)自動(dòng)化

姓名

劉滿實(shí)驗(yàn)名稱(chēng)

二叉樹(shù)的相關(guān)操作實(shí)驗(yàn)類(lèi)型設(shè)計(jì)型綜合型創(chuàng)新型實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)?zāi)康模?.掌握二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)；2.掌握利用二叉樹(shù)創(chuàng)建方法3.掌握各種二叉樹(shù)的遍歷實(shí)現(xiàn)方法。實(shí)驗(yàn)要求：1.編寫(xiě)遞歸實(shí)現(xiàn)二叉樹(shù)的中序、先序和后序遍歷算法以及層次遍歷算法和二叉樹(shù)高度算法；2.編寫(xiě)主函數(shù)測(cè)試以上二叉樹(shù)的創(chuàng)建和遍歷函數(shù)。實(shí)驗(yàn)原理（算法流程）開(kāi)始

開(kāi)始輸出主菜單選擇界面輸出主菜單選擇界面輸入x的值其他：輸入x的值輸入項(xiàng)無(wú)效，x=?請(qǐng)重新選擇！x=?退出二叉樹(shù)高度層次遍歷后序遍歷中序退出二叉樹(shù)高度層次遍歷后序遍歷中序遍歷先序遍歷創(chuàng)建二叉樹(shù)輸入rturn的值輸入rturn的值rturn=N假rturn=N真結(jié)束結(jié)束組內(nèi)分工（可選）無(wú)實(shí)驗(yàn)結(jié)果分析及心得體會(huì)成績(jī)?cè)u(píng)定教師簽名：2010年月日#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX(a,b)((a)>(b)?(a):(b))/*對(duì)比較函數(shù)進(jìn)行宏定義*/#definelength100typedefchardatatype;typedefstructnode/*定義二叉樹(shù)的存儲(chǔ)方式*/{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creat_tree();/*創(chuàng)建二叉樹(shù)*/voidpreorder(bitree*p);/*對(duì)二叉樹(shù)進(jìn)行先序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/voidinorder(bitree*p);/*對(duì)二叉樹(shù)進(jìn)行中序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/voidpostorder(bitree*p);/*對(duì)二叉樹(shù)進(jìn)行后序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/voidlevelorder(bitree*p);/*對(duì)二叉樹(shù)進(jìn)行層次遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/intdepth_bitree(bitree*root);/*計(jì)算二叉樹(shù)的深度*/voidmenu(){ printf("****************************************************\n"); printf("****************1.按先序遞歸方式創(chuàng)建二叉樹(shù)**********\n"); printf("****************2.先序遍歷二叉樹(shù)********************\n"); printf("****************3.中序遍歷二叉樹(shù)********************\n"); printf("****************4.后序遍歷二叉樹(shù)********************\n"); printf("****************5.層次遍歷二叉樹(shù)********************\n"); printf("****************6.輸出二叉樹(shù)的高度******************\n"); printf("****************7.退出******************************\n"); printf("****************************************************\n");}voidmain(){ intx,k; charrturn; bitree*root; while(1) { system("cls");//清屏 menu(); printf("請(qǐng)選擇相應(yīng)功能："); fflush(stdin); scanf("%d",&x); switch(x) { case1://按先序遞歸方式創(chuàng)建二叉樹(shù) printf("請(qǐng)輸入各結(jié)點(diǎn)以完成二叉樹(shù)的創(chuàng)建：\n"); fflush(stdin); root=creat_tree(); printf("二叉樹(shù)創(chuàng)建完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case2://先序遍歷二叉樹(shù) printf("先序遍歷結(jié)果如下：\n"); preorder(root); printf("\n"); printf("先序遍歷完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case3://中序遍歷二叉樹(shù) printf("中序遍歷結(jié)果如下：\n"); inorder(root); printf("\n"); printf("中序遍歷完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case4://.后序遍歷二叉樹(shù) printf("后序遍歷結(jié)果如下：\n"); postorder(root); printf("\n"); printf("后序遍歷完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case5://層次遍歷二叉樹(shù) printf("層次遍歷結(jié)果如下：\n"); levelorder(root); printf("\n"); printf("層次遍歷完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case6://輸出二叉樹(shù)的高度 k=depth_bitree(root); printf("二叉樹(shù)的高度為：\n"); printf("%d",k); printf("\n"); printf("二叉樹(shù)的高度輸出完成,是否繼續(xù)？（N退出，任意鍵繼續(xù)）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case7://退出 return; default: printf("輸入選項(xiàng)無(wú)效！請(qǐng)重新輸入！\n"); system("pause"); } } return;}bitree*creat_tree()/*創(chuàng)建二叉樹(shù)*/{ charc; bitree*root; scanf("%c",&c); if(c=='@')root=NULL;/*此時(shí)為空樹(shù)*/ else { root=(bitree*)malloc(sizeof(bitree));/*遞歸算法創(chuàng)建二叉樹(shù)*/ root->data=c; root->lchild=creat_tree(); root->rchild=creat_tree();}return(root);/*返回根結(jié)點(diǎn)指針*/}voidpreorder(bitree*p)/*對(duì)二叉樹(shù)進(jìn)行先序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/{ if(p!=NULL)/*判斷二叉樹(shù)為非空樹(shù)*/ { printf("%c",p->data);/*采用遞歸算法先序遍歷二叉樹(shù)*/ preorder(p->lchild); preorder(p->rchild); } return;}voidinorder(bitree*p)/*對(duì)二叉樹(shù)進(jìn)行中序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/{ if(p!=NULL)/*判斷二叉樹(shù)為非空樹(shù)*/ { inorder(p->lchild);/*采用遞歸算法中序遍歷二叉樹(shù)*/ printf("%c",p->data); inorder(p->rchild); } return;}voidpostorder(bitree*p)/*對(duì)二叉樹(shù)進(jìn)行后序遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/ { if(p!=NULL)/*判斷二叉樹(shù)為非空樹(shù)*/ { postorder(p->lchild);/*采用遞歸算法后序遍歷二叉樹(shù)*/ postorder(p->rchild); printf("%c",p->data); } return;}voidlevelorder(bitree*p)/*對(duì)二叉樹(shù)進(jìn)行層次遍歷，p指向二叉樹(shù)的根結(jié)點(diǎn)*/{ bitree*queue[length],*q; intfront,rear; front=rear=0; if(p!=NULL)/*判斷二叉樹(shù)為非空樹(shù)*/ { queue[rear++]=p;/*采用隊(duì)列，及遞歸算法對(duì)二叉樹(shù)進(jìn)行層次遍歷*/ while(front!=rear) { q=queue[front++]; printf("%c",q->data); if(q->lchild!=NULL)queue[rear++]=q->lchild; if(q-