數(shù)據(jù)結構實習分析報告

1、實習報告一：需求分析差不多要求以回車(n)為輸入結束標志,輸入數(shù)列L，生成一棵二叉排 序樹T；對二叉排序樹T作中序遍歷，輸出結果；輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；數(shù)據(jù)類型要實現(xiàn)二叉排序數(shù)，必須先定義數(shù)據(jù)類型，本設計的輸入數(shù)據(jù)為整型，輸出的數(shù)據(jù)也為整型。題目功能詳細講明 要生成一棵二叉排序數(shù)T，元素類型為ElemType 在二叉排序樹中查找其關鍵字等于給定值的結點是否存在 在二叉排序樹中插入一個新結點，中序遍歷所建二叉排序樹，將得到一個按關鍵字有序的元素序列 二叉排序樹的查找，可多次查找，并輸出查找的結果4最后對輸出

2、結構進行分析二概要分析1.二叉樹是另一種樹型結構，他的特點是每個結點至多只有兩棵子樹，同時，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.二叉樹的存儲結構/-二叉樹的順序存儲表示-#define MAX-TREE-SIZE 100 /二叉樹的最大結點數(shù)Typedef TELem type sqbitreeMAX-TREE-SIZE;/0號單元存儲根結點sqBiTree bt3.在不同的存儲結構中,實現(xiàn)二叉樹的操作方法也不同,如找結點X的雙親PARENT(T,E),在三叉鏈表中專門容易實現(xiàn),而在二叉鏈表中則需從根指針動身巡查.4. if(!t) *p=f;return (0); /*查找不成功

3、*/else if(key=t-data) *p=t;return (1); /*查找成功*/ else if(keydata) searchBST(t-lchild,key,t,p); /*在左子樹中接著查找*/else searchBST(t-rchild,key,t,p); /*在右子樹中接著查找*/5calculateASL(node *t,int *s,int *j,int i) /*計算平均查找長度*/ if(*t) i+; /*i記錄當前結點的在當前樹中的深度*/ *s=*s+i; /*s記錄已遍歷過的點的深度之和*/ if(calculateASL(&(*t)-lchild,s

4、,j,i)/*計算左子樹的ASL*/三.詳細程序#include# include typedef struct Tnode int data; /*輸入的數(shù)據(jù)*/ struct Tnode *lchild,*rchild; /*結點的左右指針，分不指向結點的左右小孩*/ *node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函數(shù)*/ if(!t) *p=f;return (0); /*查找不成功*/else if(key=t-data) *p=t;return (1); /*查找成功*/ else if(keydata) sea

5、rchBST(t-lchild,key,t,p); /*在左子樹中接著查找*/else searchBST(t-rchild,key,t,p); /*在右子樹中接著查找*/ insertBST(node *t,int key) /*插入函數(shù)*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node)malloc(sizeof(BSTnode); s-data=key; s-lchild=s-rchild=NULL; if(!p) *t=s; /*被插結點*s為新的根結點*/ else if(keydata) p-

6、lchild=s;/*被插結點*s為左小孩*/ else p-rchild=s; /*被插結點*s為右小孩*/ return (1); else return (0);/*樹中已有關鍵字相同的結點，不再插入*/ inorderTraverse(node *t) /*中序遍歷函數(shù)*/ if(*t) if(inorderTraverse(&(*t)-lchild) /*中序遍歷根的左子樹*/ printf(%d ,(*t)-data); /*輸出根結點*/ if(inorderTraverse(&(*t)-rchild); /*中序遍歷根的右子樹*/ return(1) ; calculateAS

7、L(node *t,int *s,int *j,int i) /*計算平均查找長度*/ if(*t) i+; /*i記錄當前結點的在當前樹中的深度*/ *s=*s+i; /*s記錄已遍歷過的點的深度之和*/ if(calculateASL(&(*t)-lchild,s,j,i)/*計算左子樹的ASL*/ (*j)+; /*j記錄樹中結點的數(shù)目*/ if(calculateASL(&(*t)-rchild,s,j,i) /*計算右子樹的ASL*/ i-; return(1); else return(1); node Delete(node t,int key) /*刪除函數(shù)*/ node p=

8、t,q=NULL,s,f; while(p!=NULL) /*查找要刪除的點*/ if(p-data=key) break; q=p; if(p-datakey) p=p-lchild; else p=p-rchild; if(p=NULL) return t; /*查找失敗*/ if(p-lchild=NULL) /*p指向當前要刪除的結點*/ if(q=NULL) t=p-rchild; /*q指向要刪結點的父母*/ else if(q-lchild=p) q-lchild=p-rchild; /*p為q的左小孩*/ else q-rchild=p-rchild;/*p為q的右小孩*/ f

9、ree(p); else /*p的左小孩不為空*/ f=p; s=p-lchild; while(s-rchild) /*左拐后向右走到底*/ f=s; s=s-rchild; if(f=p) f-lchild=s-lchild; /*重接f的左子樹*/ else f-rchild=s-lchild; /*重接f的右子樹*/ p-data=s-data; free (s); return t; int balanceBST(node t,int *i) /*推斷是否為平衡二叉樹的函數(shù)*/ int dep1,dep2; if(!t) return(0); else dep1=balanceBST

10、(t-lchild,i); dep2=balanceBST(t-rchild,i); if(dep1-dep2)1|(dep1-dep2)dep2) return(dep1+1); else return(dep2+1);void main() node T=NULL; int num; int s=0,j=0,i=0; int ch=0; node p=NULL; printf(please input a list of numbers end with zero:); do scanf(%d,&num); if(!num) printf(you have finished your in

11、put!n); else insertBST(&T,num); while(num); printf(nn-the menu of the opperation-n); /*主程序菜單*/ printf(n 0: exit ); printf(n 1: inorder travel the tree); printf(n 2: the average search length for the tree); printf(n 3: delete); printf(n 4: judge the balance); while(ch=ch) printf(n choose the opperati

12、on to continue:); scanf(%d,&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf( The result of the inorder traverse is:n ); inorderTraverse(&T); /*1中序遍歷*/ break; case 2: s=0;j=0;i=0; calculateASL(&T,&s,&j,i); /*2計算平均查找長度*/ printf( ASL=%d/%d,s,j); break; case 3: printf( Please input the number yo

13、u want to delete:); scanf(%d,&num); /*3刪除某個結點*/ if(searchBST(T,num,NULL,&p) T=Delete(T,num); printf( You have delete the number successfully!n ); inorderTraverse(&T); else printf( No node %d you want to delete!,num); break; case 4: i=0; balanceBST(T,&i); /*推斷是否為平衡二插樹*/ if(i=0) printf( OK!The tree is

14、 a balanced tree!); else printf( NO!); break; default: printf(Your input is wrong!please input again!n); break; /*輸入無效字符*/ 四.結果輸出112 5 4 1 6 0You have finished your input!-the menu of the opperation-0: exit1: inorder travel the tree2: the average search length for the tree3:delete4: judge the balanc

15、eChoose the opperation to continue:1The result of the inorder traverse is:4 5 6 113Choose the opperation to continue2ASL=13/5Choose the opperation to continue:3Please input the number you want to delete:6You have delete the number successfully!4 5 113Choose the opperation to continue:4NO!Choose the opperation to continue:0Press any key to con