實 驗 報 告 實驗課程：數 據 結 構 實驗項目：實驗四二叉排序樹應用 專 業(yè)：計算機科學與技術 班 級： 姓 名： 學 號： 指導教師： 目 錄1、 問題定義及需求分析 （1）問題描述 （2）實驗任務 （3）需求分析二、概要設計： (1)抽象數據類型定義 (2)主程序流程 (3) 模塊關系3、 詳細設計 (1)數據類型及存儲結構 (2)模塊設計4、 調試分析 (1)調試分析 (2)算法時空分析 (3)經驗體會5、 使用說明 (1)程序使用說明6、 測試結果 (1)運行測試結果截圖7、 附錄 (1)源代碼1、 問題定義及需求分析（1）實驗目的 二叉排序樹應用 問題描述 互聯網域名系統(tǒng)是一個典型的樹形層次結構。從根節(jié)點往下的第一層是頂層域，如cn、com等，最底層（第四層）是葉子結點，如www等。因此，域名搜索可以構造樹的結構完成；（2）實驗任務 設計基于二叉排序樹的搜索互聯網域名的程序。（3）需求分析： 1）采用二叉樹的二叉鏈表存儲結構。 2）完成二叉排序樹的創(chuàng)建、插入、刪除、查詢操作。 3）可以考慮兩棵二叉排序樹的合并。2、 概要設計：(1)抽象數據類型定義： 程序中定義了二叉排序樹的節(jié)點類型；由數據域和左右孩子指針構成；指針類型為該節(jié)點類型，指向該類型的節(jié)點形成二叉排序樹；數據域是由字符數組構成，用于存儲節(jié)點數據信息。(2) 主程序流程： 輸入域名 拆分域名并完成二叉排序樹的創(chuàng)建 調用功能函數進入功能菜單 選擇執(zhí)行不同的操作(查找、插入、刪除) 操作完畢后可選擇返回功能函數繼續(xù)執(zhí)行操作或者結束程序 (3) 模塊間的調用關系: 創(chuàng)建二叉排序樹 功能函數 查找 插入 刪除 選擇 結束 三、詳細設計 采用二叉鏈表存儲結構的二叉排序樹的定義如下： typedef struct BiTNodeElemType data30; /定義數據域類型為字符數組 struct BiTNode *lchild, *rchild; /定義左右孩子節(jié)點指針BiTNode, *BiTree;模塊1-查找樹中是否有待插入節(jié)點算法如下：int SearchBST(BiTree T, char *key, BiTree f, BiTree *p) if (!T) /* 查找不成功 */ *p = f; return 0; else if(strcmp(key,T-data)=0) /* 查找成功 */ *p = T; return 1; else if (strcmp(key,T-data)lchild, key, T, p); /* 若該節(jié)點小于當前節(jié)點，則在左子樹中繼續(xù)查找 */ else return SearchBST(T-rchild, key, T, p); /* 否則在右子樹中繼續(xù)查找 */模塊2-插入節(jié)點算法如下：int InsertBST(BiTree *T, char *key) BiTree p,s; if (!SearchBST(*T, key, NULL, &p) /* 查找不成功 */ s = (BiTNode*)malloc(sizeof(BiTNode);strcpy(s-data, key); s-lchild = s-rchild = NULL; if (!p) *T = s; /* 插入s為新的根結點 */ else if (strcmp(key,p-data)lchild = s; /* 插入s為左孩子 */ else p-rchild = s; /* 插入s為右孩子 */ return 1; else return 0; /* 樹中已有關鍵字相同的結點，不再插入 */模塊3-刪除節(jié)點算法如下：int Delete(BiTree *p) BiTree q,s; if(*p)-rchild=NULL) /* 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支) */ q=*p;*p=(*p)-lchild;free(q); else if(*p)-lchild=NULL) /* 只需重接它的右子樹 */ q=*p; *p=(*p)-rchild; free(q); else /* 左右子樹均不空 */ q=*p; s=(*p)-lchild; while(s-rchild) /* 轉左，然后向右到盡頭（找待刪結點的前驅） */ q=s; s=s-rchild; strcpy(*p)-data,s-data); /* s指向被刪結點的直接前驅（將被刪結點前驅的值取代被刪結點的值） */ if(q!=*p) q-rchild=s-lchild; /* 重接q的右子樹 */ else q-lchild=s-lchild; /* 重接q的左子樹 */ free(s); return 1;模塊4-查找待刪除節(jié)點的位置算法如下：int DeleteBST(BiTree *T,char *key) if(!*T) /* 不存在關鍵字等于key的數據元素 */ return 0; else if (strcmp(key,(*T)-data)=0) /* 找到關鍵字等于key的數據元素 */ return Delete(T); else if (strcmp(key,(*T)-data)lchild,key);/* 若待刪除節(jié)點大于當前節(jié)點，則遞歸訪問其左子樹 */ else return DeleteBST(&(*T)-rchild,key);/* 否則訪問右子樹 */ 模塊5-功能函數包括查找、插入和刪除算法如下:void Gongneng(BiTNode *A)/ 執(zhí)行操作需將此樹的根節(jié)點傳入到此函數里面int k;char a30,c30,d30;printf(請選擇你的操作：n);printf(1-查找n);printf(2-刪除n);printf(3-插入n);printf(輸入：);scanf(%d,&k);switch(k)/通過switch語句執(zhí)行不同的操作case 1 :system(cls);printf(請輸入你要查找的節(jié)點：);scanf(%s,c); Search(A, c); /調用查找函數 break;case 2:system(cls);printf(請輸入你要刪除的節(jié)點：);scanf(%s,a);if(!DeleteBST(&A,a)printf(n不存在此節(jié)點！n);elseprintf(n刪除節(jié)點成功！nn刪除后樹的中序遍歷結果如下：n);InOrder(A); break;case 3:system(cls);printf(請輸入要插入的節(jié)點：);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失敗!要插入的節(jié)點已存在!n);elseprintf(n插入成功!nn插入后樹的中序遍歷結果如下：n); InOrder(A);break; default : printf(輸入數值錯誤!n);四、調試分析 問題及解決方法： 在編寫功能函數時，在參數的傳遞上出現了問題；無法正確的將根節(jié)點傳入到功能函數里，導致功能函數無法正常運行；解決方法為：void Gongneng(BiTNode *A)； 時空分析： 由于采用二叉鏈表的存儲結構，所以在插入和刪除算法的時間復雜度較低；而對于較多的數據元素形成的樹時，查找算法在時間復雜度上不算簡便；而存儲方面，二叉鏈表構成的二叉排序樹存儲較為方便且空間利用率高； 經驗體會: 二叉鏈表存儲結構的存儲密度較高，使用起來較為方便；而且在處理數據方面，二叉鏈表存儲結構的處理性比較好，尤其是對插入和刪除算法；五、使用說明第一步：點擊運行按鈕；第二步: 輸入待輸入的域名個數k；第三步：依次輸入k個域名；第四步：回車，程序跳轉至功能界面，根據提示輸入想要執(zhí)行的功能選項序號；第五步：回車后，針對各功能項有提示藥查找、插入或者刪除的節(jié)點；第六步： 執(zhí)行功能后，選擇結束運行還是繼續(xù)操作；第七步：若選擇繼續(xù)操作，則程序進入功能界面，可繼續(xù)選擇執(zhí)行的功能；第八步：循環(huán)執(zhí)行第四到七步；第九步：可在第六步選擇退出程序；六、測試結果七、附錄源代碼：#include#include#include#define ElemType chartypedef struct BiTNodeElemType data30; /定義數據域類型為字符數組 struct BiTNode *lchild, *rchild; /定義左右孩子節(jié)點指針BiTNode, *BiTree;int SearchBST(BiTree T, char *key, BiTree f, BiTree *p) if (!T) / 樹為空，查找不成功 *p = f; return 0; else if(strcmp(key,T-data)=0) / 查找成功 *p = T; /p指向查找到的節(jié)點 return 1; else if (strcmp(key,T-data)lchild, key, T, p); / 在左子樹中繼續(xù)查找 else return SearchBST(T-rchild, key, T, p); / 在右子樹中繼續(xù)查找 int InsertBST(BiTree *T, char *key) BiTree p,s; if (!SearchBST(*T, key, NULL, &p) / 查找不成功 s = (BiTNode*)malloc(sizeof(BiTNode);/s作為插入節(jié)點strcpy(s-data, key); s-lchild = s-rchild = NULL; if (!p) *T = s; / 插入s為新的根結點 else if (strcmp(key,p-data)lchild = s; / 插入s為左孩子 else p-rchild = s; / 插入s為右孩子 return 1; else return 0; / 樹中已有關鍵字相同的結點，不再插入int Search(BiTNode *N,char *key) / 查找樹中是否存在要插入的節(jié)點 BiTNode *M; M=N; while(M!=NULL&strcmp(M-data,key)!=0) / 查找終止條件為樹為空或者查找的節(jié)點數據與待查找的數據相同 if(strcmp(M-data,key)rchild; / 繼續(xù)查找左子樹 else M=M-lchild; / 繼續(xù)查找右子樹 if(!M) printf(查找失??！n); else printf(查找成功！n);/* 從二叉排序樹中刪除結點p，并重接它的左或右子樹。 */int Delete(BiTree *p) BiTree q,s; if(*p)-rchild=NULL) / 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支) q=*p;*p=(*p)-lchild;free(q); / 釋放該節(jié)點 else if(*p)-lchild=NULL) / 只需重接它的右子樹 q=*p; *p=(*p)-rchild; free(q); / 釋放該節(jié)點 else / 左右子樹均不空 q=*p; s=(*p)-lchild; while(s-rchild) / 轉左，然后向右到盡頭（找待刪結點的前驅) q=s; s=s-rchild; strcpy(*p)-data,s-data); / s指向被刪結點的直接前驅（將被刪結點前驅的值取代被刪結點的值） if(q!=*p) q-rchild=s-lchild; / 重接q的右子樹 else q-lchild=s-lchild; /重接q的左子樹 free(s); return 1;int DeleteBST(BiTree *T,char *key) if(!*T) /不存在關鍵字等于key的數據元素 return 0; else if (strcmp(key,(*T)-data)=0) /找到關鍵字等于key的數據元素 return Delete(T); /調用Delete函數刪除該節(jié)點 else if (strcmp(key,(*T)-data)lchild,key);/ 繼續(xù)訪問左子樹 else return DeleteBST(&(*T)-rchild,key);/繼續(xù)訪問右子樹 void InOrder (BiTNode *root) /中序遍歷該二叉排序樹if (!root) return ; /遞歸結束條件InOrder (root-lchild); /遞歸訪問左子樹printf (%sn, root-data);/訪問根節(jié)點信息InOrder (root-rchild);/遞歸訪問右子樹void Gongneng(BiTNode *A)int k;char a30,c30,d30;printf(請選擇你的操作：n);printf(1-查找n);printf(2-刪除n);printf(3-插入n);printf(輸入：);scanf(%d,&k);switch(k)case 1 :system(cls);printf(請輸入你要查找的節(jié)點：);scanf(%s,c); Search(A, c);/調用查找函數 break;case 2:system(cls);printf(請輸入你要刪除的節(jié)點：);scanf(%s,a);if(!DeleteBST(&A,a)printf(n不存在此節(jié)點！n);elseprintf(n刪除節(jié)點成功！nn刪除后樹的中序遍歷結果如下：n);InOrder(A);/刪除后，進行一次遍歷檢查刪除后的二叉排序樹 break;case 3:system(cls);printf(請輸入要插入的節(jié)點：);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失敗!要插入的節(jié)點已存在!n);elseprintf(n插入