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