|
《數(shù)據(jù)結(jié)構(gòu)與算法》 上 機 實 驗 報 告 （請雙面打印） 實驗內(nèi)容 二叉樹的基本操作 題 目 BinarySearch Tree的建立與遍歷 指導(dǎo)教師 上機日期 學(xué) 院 信息與通信工程學(xué)院 學(xué)生姓名 班 級 學(xué) 號 成 績 指導(dǎo)老師簽字
《數(shù)據(jù)結(jié)構(gòu)與算法》上機實驗二 | 題目 | | | 1. 熟悉VC6.0編程環(huán)境； 2. 掌握Binary Search Tree的基本特性，掌握二叉樹的遍歷方法； 3. 加深對二叉樹的理解，逐步培養(yǎng)解決問題的編程能力。 | | 參考給定的程序，實現(xiàn)Binary Search Tree的建立與遍歷。要求如下： 1. 數(shù)據(jù)結(jié)點不少于10； 2. 數(shù)據(jù)中不要包括重復(fù)的數(shù)據(jù)； 3. 請數(shù)據(jù)結(jié)點保存在數(shù)組中，依次插入數(shù)據(jù)； 4. 二叉樹的存儲結(jié)構(gòu)為二叉鏈表； 5. 對二叉樹進(jìn)行先序遍歷并在屏幕上輸出該序列； 6. 對二叉樹進(jìn)行中序遍歷并在屏幕上輸出該序列； 7. 對二叉樹進(jìn)行后序遍歷并在屏幕上輸出該序列； 提示： 1. 參考課本P10； 2. 先序、中序、后序遍歷可參考PPT6.3 章第8頁。 提高選做: 1. 實現(xiàn)查找函數(shù)。 | | 裝有Visual C＋＋6.0或Visual Studio 2010的計算機一臺。 | | [1] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu) (C語言版) [M]. 北京: 清華大學(xué)出版社, 2015. [2] 譚浩強. 《C語言程序設(shè)計》(第二版)[M].北京: 清華大學(xué)出版社, 2005. | 上機實驗進(jìn)度計劃（起止時間、工作內(nèi)容） | | | | | | | | |
一、請簡單手寫出二叉樹的條性質(zhì) 請預(yù)留足夠多的空白，打印之后再手寫。 1. 二叉樹的第k層最多有___________個結(jié)點； 2. 深度為k的二叉樹最多有_________個結(jié)點； 3. 請簡要證明二叉樹的第3條性質(zhì)； 二、上機程序與問題 請將原程序、各個問題的答案寫在程序中，并直接拷在此處。 #include<stdlib.h> #include<stdio.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElementType; //? typedef int Status; //? typedef struct TreeNode* Position; //? 用Position代替TreeNode*，實現(xiàn)結(jié)構(gòu)體指針 typedef struct TreeNode* BSTree; //? 用BSTree代替TreeNode*，實現(xiàn)結(jié)構(gòu)體指針 // 下面幾句話的作用是什么？ struct TreeNode{ ElementType Element;//? 定義一個整形變量Element struct TreeNode* Left;//? 創(chuàng)建一個指向左支路的指針 struct TreeNode* Right; }; // 問題: 簡述下述函數(shù)的功能,并指出輸入和輸出分別是什么？ BSTree Insert(ElementType X, BSTree T){ if (T==NULL){ // 問題：本部分的作用？ 判斷T指針是否有指向的內(nèi)存空間，若沒有則分配 T=(BSTree)malloc(sizeof(structTreeNode)); //? 給指針T分配空間 if (T==NULL) exit(OVERFLOW);//? 異常中止 else{ T->Element=X; T->Left=NULL; T->Right=NULL; } } else{ // 問題：本部分的作用？ 根據(jù)傳進(jìn)來的參數(shù)，決定左支路或者右支路 if(X<T->Element) T->Left=Insert(X,T->Left);//? 給T加一個左支路 else if(X>T->Element) T->Right=Insert(X,T->Right); } return T; // 請問：返回的T代表什么意思？ 樹的節(jié)點 } void Traverse (BSTree T)//先序遍歷 { if(T) { printf("%d ",T->Element); Traverse(T->Left); Traverse(T->Right); } } void zhong (BSTree T)//中序遍歷 { if(T) { zhong(T->Left); printf("%d ",T->Element); zhong(T->Right); } } void hou(BSTree T)//后序遍歷 { if(T) { hou(T->Left); hou(T->Right); printf("%d ",T->Element); } } void main() { int seq[10]={35, 27,19, 0, 32, 12, 87, 26, 5, 41}; // 輸入序列數(shù)據(jù) BSTree T=NULL; //? 創(chuàng)建一個結(jié)構(gòu)體指針T // 下面這3句話產(chǎn)生的效果是什么？ 按照Insert函數(shù)分配支路 for (int i=0; i<10;i++){ T=Insert(seq, T); } printf("\n先序遍歷輸出序列為:\n"); // 先編子程序，然后在這里調(diào)用子程序，實現(xiàn)二叉樹的先序遍歷 Traverse(T); printf("\n中序遍歷輸出序列為:\n"); // 先編子程序，然后在這里調(diào)用子程序，實現(xiàn)二叉樹的中序遍歷 zhong(T); printf("\n后序遍歷輸出序列為:\n"); // 先編子程序，然后在這里調(diào)用子程序，實現(xiàn)二叉樹的后序遍歷 hou(T); // 提高題（不要求同學(xué)必須完成）： // 如果以上程序均已完成,嘗試寫出Find函數(shù) // Find函數(shù)實現(xiàn)的功能是：在上述二叉樹T中查找某個數(shù)X,如果查找成功，則返回X的地址；否則，返回NULL； //先編子程序，然后在這里調(diào)用子程序，輸出返回的地址 } if(T==NULL) printf(0): else if(T->Element==X) printf(sd,D); else if (X< T->Element) find(Xx,T->Left); else find(X,T->Right): return 0; void main() { int seq[10]={ 35,27,19,0,32,12,87,26,5,41}; BSTree T=NULL; for(int i=0;i< 10;i++){ T=Insert(seq,T);//將數(shù)字填入二叉樹 printf("\n先序遍歷輸出序列為:\n"); Traverse(T);//調(diào)用子程序,實現(xiàn)叉樹的先序遍歷 printf("\n中序遍歷輸出序列為:\n"); zhong(T);//調(diào)用子程序,實現(xiàn)叉樹的中序遍歷 printf("\n后序遍歷輸出序列為:\n"); hou(T);//調(diào)用子程序,實現(xiàn)二叉樹的后序遍歷 int X; printf("n輸入要查找的數(shù):"); scanf("%d",&X); find(x,T); } 三、結(jié)果 1. 畫出你的二叉樹，寫出你的先序、中序、后序遍歷結(jié)果。 2. 貼出你的實驗結(jié)果。注意：圖片要有圖標(biāo)和圖題，圖片處理一下，避免大片的黑色。 3. 從程序上看，如果數(shù)據(jù)中有重復(fù)的數(shù)據(jù)，程序是怎么處理的？
四、遇到的問題、解決方法與個人心得。
| 
