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

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

年級10級班號5

學(xué)號

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

姓名

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

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

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