數(shù)據(jù)結(jié)構(gòu)+設(shè)計(jì)論文+二叉排序樹的實(shí)現(xiàn)

1、實(shí)習(xí)報(bào)告一：需求分析1 基本要求a) 以回車('n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排 序樹T；b) 對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；c) 輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無(wú)x”；2 數(shù)據(jù)類型要實(shí)現(xiàn)二叉排序數(shù)，必須先定義數(shù)據(jù)類型，本設(shè)計(jì)的輸入數(shù)據(jù)為整型，輸出的數(shù)據(jù)也為整型。3 題目功能詳細(xì)說(shuō)明 要生成一棵二叉排序數(shù)T，元素類型為ElemType 在二叉排序樹中查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)是否存在 在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，中序遍歷所建二叉排序樹，將得到一個(gè)按關(guān)鍵字有序的元素序列 二叉排序樹

2、的查找，可多次查找，并輸出查找的結(jié)果4最后對(duì)輸出結(jié)構(gòu)進(jìn)行分析二概要分析1.二叉樹是另一種樹型結(jié)構(gòu)，他的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.二叉樹的存儲(chǔ)結(jié)構(gòu)/-二叉樹的順序存儲(chǔ)表示-#define MAX-TREE-SIZE 100 /二叉樹的最大結(jié)點(diǎn)數(shù)Typedef TELem type sqbitreeMAX-TREE-SIZE;/0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)sqBiTree bt3.在不同的存儲(chǔ)結(jié)構(gòu)中,實(shí)現(xiàn)二叉樹的操作方法也不同,如找結(jié)點(diǎn)X的雙親PARENT(T,E),在三叉鏈表中很容易實(shí)現(xiàn),而在二叉鏈表中則需從根指針出發(fā)巡查.4. if(!t) *

3、p=f;return (0); /*查找不成功*/else if(key=t->data) *p=t;return (1); /*查找成功*/ else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子樹中繼續(xù)查找*/else searchBST(t->rchild,key,t,p); /*在右子樹中繼續(xù)查找*/5calculateASL(node *t,int *s,int *j,int i) /*計(jì)算平均查找長(zhǎng)度*/ if(*t) i+; /*i記錄當(dāng)前結(jié)點(diǎn)的在當(dāng)前樹中的深度*/ *s=*s+i; /*s記

4、錄已遍歷過的點(diǎn)的深度之和*/ if(calculateASL(&(*t)->lchild,s,j,i)/*計(jì)算左子樹的ASL*/三.詳細(xì)程序#include<stdio.h># include<stdlib.h> typedef struct Tnode int data; /*輸入的數(shù)據(jù)*/ struct Tnode *lchild,*rchild; /*結(jié)點(diǎn)的左右指針，分別指向結(jié)點(diǎn)的左右孩子*/ *node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函數(shù)*/ if(!t) *p=f;ret

5、urn (0); /*查找不成功*/else if(key=t->data) *p=t;return (1); /*查找成功*/ else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子樹中繼續(xù)查找*/else searchBST(t->rchild,key,t,p); /*在右子樹中繼續(xù)查找*/ insertBST(node *t,int key) /*插入函數(shù)*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node

6、)malloc(sizeof(BSTnode); s->data=key; s->lchild=s->rchild=NULL; if(!p) *t=s; /*被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)*/ else if(key<p->data) p->lchild=s;/*被插結(jié)點(diǎn)*s為左孩子*/ else p->rchild=s; /*被插結(jié)點(diǎn)*s為右孩子*/ return (1); else return (0);/*樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入*/ inorderTraverse(node *t) /*中序遍歷函數(shù)*/ if(*t) if(inorderT

7、raverse(&(*t)->lchild) /*中序遍歷根的左子樹*/ printf("%d ",(*t)->data); /*輸出根結(jié)點(diǎn)*/ if(inorderTraverse(&(*t)->rchild); /*中序遍歷根的右子樹*/ return(1) ; calculateASL(node *t,int *s,int *j,int i) /*計(jì)算平均查找長(zhǎng)度*/ if(*t) i+; /*i記錄當(dāng)前結(jié)點(diǎn)的在當(dāng)前樹中的深度*/ *s=*s+i; /*s記錄已遍歷過的點(diǎn)的深度之和*/ if(calculateASL(&(*t

8、)->lchild,s,j,i)/*計(jì)算左子樹的ASL*/ (*j)+; /*j記錄樹中結(jié)點(diǎn)的數(shù)目*/ if(calculateASL(&(*t)->rchild,s,j,i) /*計(jì)算右子樹的ASL*/ i-; return(1); else return(1); node Delete(node t,int key) /*刪除函數(shù)*/ node p=t,q=NULL,s,f; while(p!=NULL) /*查找要?jiǎng)h除的點(diǎn)*/ if(p->data=key) break; q=p; if(p->data>key) p=p->lchild; el

9、se p=p->rchild; if(p=NULL) return t; /*查找失敗*/ if(p->lchild=NULL) /*p指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)*/ if(q=NULL) t=p->rchild; /*q指向要?jiǎng)h結(jié)點(diǎn)的父母*/ else if(q->lchild=p) q->lchild=p->rchild; /*p為q的左孩子*/ else q->rchild=p->rchild;/*p為q的右孩子*/ free(p); else /*p的左孩子不為空*/ f=p; s=p->lchild; while(s->rchil

10、d) /*左拐后向右走到底*/ 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(t->lchild,i); dep2=balan

11、ceBST(t->rchild,i); if(dep1-dep2)>1|(dep1-dep2)<-1) *i=dep1-dep2;/*用i值記錄是否存在不平衡現(xiàn)象*/ if(dep1>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(&quo

12、t;%d",&num); if(!num) printf("you have finished your input!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 se

13、arch length for the tree"); printf("n 3: delete"); printf("n 4: judge the balance"); while(ch=ch) printf("n choose the opperation to continue:"); scanf("%d",&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf(" The result of the inorder trav

14、erse is:n "); inorderTraverse(&T); /*1中序遍歷*/ break; case 2: s=0;j=0;i=0; calculateASL(&T,&s,&j,i); /*2計(jì)算平均查找長(zhǎng)度*/ printf(" ASL=%d/%d",s,j); break; case 3: printf(" Please input the number you want to delete:"); scanf("%d",&num); /*3刪除某個(gè)結(jié)點(diǎn)*/ if(se

15、archBST(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 a balanced

16、 tree!"); else printf(" NO!"); break; default: printf("Your input is wrong!please input again!n"); break; /*輸入無(wú)效字符*/ 四.結(jié)果輸出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:delete

17、4: judge the balanceChoose the opperation to continue:1The result of the inorder traverse is:1 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!1 4 5 113Choose the opperation to continue:4NO!Choose the opperation