關(guān)于二叉排序樹的實現(xiàn)

1、 課程設(shè)計報告 關(guān)于二叉排序樹的實現(xiàn)一：需求分析1：基本要求a) 以回車('n')為輸入結(jié)束標志,輸入數(shù)列L，生成一棵二叉排 序樹T；b) 對二叉排序樹T作中序遍歷，輸出結(jié)果；c) 輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；2：設(shè)計要求：(1) 符合課題要求，實現(xiàn)相應(yīng)功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實用性、安全性。3:設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)1:利用數(shù)組思想,通過改變數(shù)組指針來表示數(shù)組的左右子樹,左子樹的下標為2*i,右子樹的下標為2*i+1. 2：樹的存儲結(jié)構(gòu)如下： #defin

2、e N 100 /*二叉樹結(jié)點的最大數(shù)目*/typedef struct int *data; /*數(shù)組首址指針*/ int lenth; /*數(shù)組長度*/BST;4：每個模塊的功能要求: 初始化一個數(shù)組，開辟一塊內(nèi)存空間，先建立一個插入函數(shù)。 創(chuàng)建一棵二叉樹，中序遍歷該樹在二叉排序樹中查找其關(guān)鍵字等于給定值的結(jié)點是否存在刪除所給結(jié)點，并對新樹中序遍歷最后，可以判斷所給樹是否為平衡樹二：概要設(shè)計1:使用樹的動態(tài)順序存儲結(jié)構(gòu)，先初始化一個數(shù)組。2：建立一個插入函數(shù)，通過調(diào)用該函數(shù)邊查找邊插入建立二叉排序樹3：通過遞歸調(diào)用，中序遍歷樹，以及判斷其是否為平衡樹4：q.data=(int *)mall

3、oc(N*sizeof(int); /*重新初始化一個數(shù)組Q*/新的數(shù)組儲存刪除給定結(jié)點的新樹5：要實現(xiàn)二叉排序樹，要先創(chuàng)建二叉排序樹，在以下程序中利用邊查找邊插入來建立二叉排序樹。BST create(int *crew,int num) /*創(chuàng)建二叉排序樹的函數(shù)*/ BST T; int i,j; T.data=(int *)malloc(N*sizeof(int); /*數(shù)組初始化*/ for(j=0;j<N;j+) T.dataj=0; T.lenth=0; for(i=0;i<num;i+) /*邊查找邊插入建立二插排序樹*/ insert(T,1,crewi); +T.

4、lenth; /*記錄樹中結(jié)點的個數(shù)*/ return (T);在這個過程中，調(diào)用了已經(jīng)建立的函數(shù)insert(T,1,crewi); 為新結(jié)點查找到相應(yīng)的位置，將其插入樹中。6：中序遍歷二叉排序樹的結(jié)果應(yīng)該是一列從小到大排列的數(shù)7：在刪除函數(shù)中，要保證刪除后得到的二叉樹依然是二叉排序樹，在下列程序中是利用重建一個新的二叉樹，將不刪除的元素復(fù)制到該樹中。BST cancle(BST T,int key) /*刪除函數(shù)*/ BST q; int i; q.data=(int *)malloc(N*sizeof(int); /*重新初始化一個鏈表Q*/ for(i=0;i<N;i+) q.d

5、atai=0; q.lenth=0; for(i=1;i<N&&T.lenth>0;i+)/*T中不為要刪結(jié)點的元素全部復(fù)制到Q*/ if(T.datai=0|T.datai=key) continue; insert(q,1,T.datai); -T.lenth; +q.lenth; return(q);5：判斷一棵樹是否為平衡二叉樹，看其左右子樹的高度之差的絕對值是否小于等于1。 dep1=balanceBST(T,T.data2*i,k); dep2=balanceBST(T,T.data2*i+1,k); if(dep1-dep2)>1|(dep1-d

6、ep2)<-1) *k=dep1-dep2;/*用k值記錄是否存在不平衡現(xiàn)象*/ if(dep1>dep2) return(dep1+1);else return(dep2+1);6：主函數(shù)利用switch語句實現(xiàn)不同函數(shù)功能的顯示。三：詳細設(shè)計#include<stdio.h>#include<stdlib.h>#define N 100 /*二叉樹結(jié)點的最大數(shù)目*/typedef struct int *data; /*數(shù)組首址指針*/ int lenth; /*數(shù)組長度*/BST;insert(BST T,int i,int key) /*插入函數(shù)*/

7、 if(i<1|i>N) printf("失敗!"); /*插入不成功*/ if(T.datai=0) T.datai=key; /*被插結(jié)點是新的根節(jié)點*/ else if(key<T.datai) insert(T,2*i,key); /*在左子樹中繼續(xù)查找相應(yīng)位置*/ else if(key>T.datai) insert(T,2*i+1,key); /*在右子樹中繼續(xù)查找*/BST create(int *crew,int num) /*創(chuàng)建二插排序樹的函數(shù)*/ BST T; int i,j; T.data=(int *)malloc(N*s

8、izeof(int); /*數(shù)組初始化*/ for(j=0;j<N;j+) T.dataj=0; T.lenth=0; for(i=0;i<num;i+) /*邊查找邊插入建立二插排序樹*/ insert(T,1,crewi); +T.lenth; /*記錄樹中結(jié)點的個數(shù)*/ return (T);inordertraverse(BST T,int i) /*中序遍歷函數(shù)*/ if(T.datai) inordertraverse(T,2*i); /*中序遍歷根的左子樹*/ printf("%d ",T.datai);/*輸出根結(jié)點*/ inordertrave

9、rse(T,2*i+1);/*中序遍歷根的右子樹*/ int search(BST T,int key,int i)/*查找函數(shù)*/ if(!T.datai) return(0); /*查找不成功*/ else if(key=T.datai) return(i);/*查找成功*/ else if(key<T.datai) search(T,key,2*i);/*在左子樹中繼續(xù)查找*/ else search(T,key,2*i+1); /*在右子樹中繼續(xù)查找*/BST cancle(BST T,int key) /*刪除函數(shù)*/ BST q; int i; q.data=(int *)m

10、alloc(N*sizeof(int); /*重新初始化一個數(shù)組Q*/ for(i=0;i<N;i+) q.datai=0; q.lenth=0; for(i=1;i<N&&T.lenth>0;i+)/*T中不為要刪結(jié)點的元素全部復(fù)制到Q*/ if(T.datai=0|T.datai=key) continue; insert(q,1,T.datai); -T.lenth; +q.lenth; return(q); int balanceBST(BST T,int i,int *k) /*判斷是否為平衡二叉樹的函數(shù)*/ int dep1,dep2; if(!T

11、.datai)return(0); else dep1=balanceBST(T,T.data2*i,k); dep2=balanceBST(T,T.data2*i+1,k); if(dep1-dep2)>1|(dep1-dep2)<-1) *k=dep1-dep2;/*用k值記錄是否存在不平衡現(xiàn)象*/ if(dep1>dep2) return(dep1+1); else return(dep2+1);void main() BST T; int crewN; int i=0; int k=0; int num,ch=0,j; printf("請輸入一串數(shù)字，以數(shù)字

12、-1結(jié)束:"); do scanf("%d",&num); if(num=-1) printf("輸入完成n"); else crewi=num; i+; while(num!=-1); T=create(crew,i); printf("nn*操作選項*");printf("n* *"); /*主程序菜單*/ printf("n* 0: 退出 *"); printf("n* 1: 中序遍歷二叉排序樹 *"); printf("n* 2: 刪除元素

13、 *"); printf("n* 3: 判斷是否為平衡樹 *"); printf("n*"); while(ch=ch) printf("n 選擇您要進行的操作:"); scanf("%d",&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf(" 中序遍歷二叉排序樹的結(jié)果:n "); inordertraverse(T,1);/*1中序遍歷*/ break; case 2: printf(" 請輸入你要刪除

14、的數(shù)字:"); scanf("%d",&num); /*3刪除某個結(jié)點*/ j=search(T,num,1); if(j) T=cancle(T,num); printf(" 刪除成功!n "); inordertraverse(T,1); i-; else printf(" 你要刪除的結(jié)點不存在!",num); break;case 3: k=0; balanceBST(T,i,&k); if(k=0) printf("是平衡樹");else printf("不是平衡樹"); break; default: printf("輸入字符無效，請重新選擇!n"); break; /*輸入無效字符*/ 四：調(diào)試分析 程序運行結(jié)果截