數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計--二叉排序樹調(diào)整為平衡二叉樹

1、精品文檔學(xué)號2021-2021學(xué)年 第一學(xué)期1208020228?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計報告題目：二叉排序樹調(diào)整為平衡二叉樹專業(yè)：網(wǎng)絡(luò)工程班級：二姓名：汪杰指導(dǎo)教師：劉義紅成績：計算機(jī)與信息工程系2021年 1 月 2日目錄1、 問題描述2、 設(shè)計思路(數(shù)學(xué)模型的選擇) 3、 二叉排序樹和平衡二叉樹定義4、 程序清單5.程序功能說明5.運(yùn)行與調(diào)試分析 6.總結(jié)1. 問題描述輸入帶排序序列生成二叉排序樹，并調(diào)整使其變?yōu)槠胶舛鏄?，運(yùn)行并進(jìn)行調(diào)試。2. 設(shè)計思路平衡二叉樹的調(diào)整方法平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個新結(jié)點(diǎn)時，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹的平衡性，假設(shè)是，那

2、么找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下： 每當(dāng)插入一個新結(jié)點(diǎn)，從該結(jié)點(diǎn)開始向上計算各結(jié)點(diǎn)的平衡因子，即計算該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子，假設(shè)該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子的絕對值均不超過1，那么平衡二叉樹沒有失去平衡，繼續(xù)插入結(jié)點(diǎn)； 假設(shè)插入結(jié)點(diǎn)的某祖先結(jié)點(diǎn)的平衡因子的絕對值大于1，那么找出其中最小不平衡子樹的根結(jié)點(diǎn)； 判斷新插入的結(jié)點(diǎn)與最小不平衡子樹的根結(jié)點(diǎn)的關(guān)系，確定是哪種類型的調(diào)整； 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原那么調(diào)整沖

3、突；如果是LR型或LR型，那么需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點(diǎn)先不動，調(diào)整插入結(jié)點(diǎn)所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原那么調(diào)整沖突；3. 二叉排序樹和平衡二叉樹定義二叉排序樹二叉排序樹Binary Sort Tree又稱二叉查找樹。它或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹：1假設(shè)左子樹不空，那么左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2） 假設(shè)右子樹不空，那么右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（3） 3左、右子樹也分別為二叉排序樹；平衡二叉樹平衡二叉樹Balanced Binary Tree 或Height-Bal

4、anced Tree又稱AVL樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉；它的左子樹右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1，平衡二叉樹上的任何節(jié)點(diǎn)的左子樹和右子樹的深度的差值只能是1、0或1。4. 程序功能說明void preorder(bintree t)/*前序遍歷*/void midorder(bintree t)/*中序遍歷*/lastorder(bintree t)/*后序遍歷bintree a;int j,k;clrscr();textcolor(2);printf(*歡送您使用本二叉樹操作系統(tǒng)*n);printf(建造一棵二叉樹請您輸入各個結(jié)點(diǎn)的元素

5、值,()表示一個空格鍵:n);printf(輸入例如:abc()()de()g()()f()()()回車:n);a=createbitree();printf(您輸入的二叉數(shù)嵌套法表示如下:n);printree(a);printf(n);printf(樹的深度為:n);j=treedepth(a);printf(%dn,j);printf(二叉數(shù)的葉子接點(diǎn)個數(shù)為:n);k=treeleaf(a);printf(%dn,k);printf(您所輸入的二叉樹的前序遍歷順序輸出如下:n);if(!a) printf(二叉樹為空n);elsepreorder(a);printf(n);printf(

6、您所輸入的二叉樹的中序遍歷順序如下輸出:n);if(!a) printf(二叉樹為空n);elsemidorder(a);printf(n);printf(您所輸入的二叉樹的后序遍歷順序輸出如下:n);if(!a) printf(二叉樹為空n);elselastorder(a);printf(n);printf(您所輸入的二叉樹的層次順序遍歷輸出如下:n); if(!a) printf(二叉樹為空n);else translevel(a);5.程序清單#include stdio.h#include conio.h#include stdlib.h#define NULL 0int leftd

7、ep,rightdep;typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bintnode,*bintree;bintree createbitree()bintree t;char x;scanf(%c,&x);if(x= ) t=NULL;elset=(bintnode *)malloc(sizeof(bintnode); t-data=x; t-lchild=createbitree(); t-rchild=createbitree();return(t);void preorder(bintree t)/*前序

8、遍歷*/if(t)printf(%2c,t-data);preorder(t-lchild);preorder(t-rchild);void midorder(bintree t)/*中序遍歷*/if(t)midorder(t-lchild); printf(%2c,t-data); midorder(t-rchild);void printree(bintree t)if(t!=NULL)printf(%c,t-data); if(t-lchild!=NULL|t-rchild!=NULL) printf();printree(t-lchild); if(t-rchild!=NULL) pr

9、intf(,); printree(t-rchild); printf();int treedepth(bintree t) if(t=NULL) return 0; elseleftdep=treedepth(t-lchild); rightdep=treedepth(t-rchild); if(leftdeprightdep)return (leftdep+1);elsereturn(rightdep+1);int treeleaf(bintree t)if(t=NULL)return0;else if(t-lchild=NULL&t-rchild=NULL) return1;else r

10、eturn(treeleaf(t-lchild)+treeleaf(t-rchild);void lastorder(bintree t)/*后序遍歷*/if(t)lastorder(t-lchild);lastorder(t-rchild);printf(%2c,t-data);void translevel(bintree t)struct bitnodebintree vec30; int f,r;q;q.f=0;q.r=0;if(t!=NULL) printf(%2c,t-data); q.vecq.r=t;q.r=q.r+1; while (q.flchild!=NULL) prin

11、tf(%2c,t-lchild-data); q.vecq.r=t-lchild; q.r=q.r+1;if(t-rchild!=NULL) printf(%2c,t-rchild-data); q.vecq.r=t-rchild; q.r=q.r+1; printf(n);main()bintree a;int j,k;clrscr();textcolor(2);printf(*歡送您使用本二叉樹操作系統(tǒng)*n);printf(建造一棵二叉樹請您輸入各個結(jié)點(diǎn)的元素值,()表示一個空格鍵:n);printf(輸入例如:abc()()de()g()()f()()()回車:n);a=createbi

12、tree();printf(您輸入的二叉數(shù)嵌套法表示如下:n);printree(a);printf(n);printf(樹的深度為:n);j=treedepth(a);printf(%dn,j);printf(二叉數(shù)的葉子接點(diǎn)個數(shù)為:n);k=treeleaf(a);printf(%dn,k);printf(您所輸入的二叉樹的前序遍歷順序輸出如下:n);if(!a) printf(二叉樹為空n);elsepreorder(a);printf(n);printf(您所輸入的二叉樹的中序遍歷順序如下輸出:n);if(!a) printf(二叉樹為空n);elsemidorder(a);printf(n);printf(您所輸入的二叉樹的后序遍歷順序輸出如下:n);if(!a) printf(二叉樹為空n);elselastorder(a);printf(n);printf(您所輸入的二叉樹的層次順序遍歷輸出如下:n); if(!a) printf(二叉樹為空n);else translevel(a);5. 運(yùn)行與調(diào)試分析輸入幾個數(shù)據(jù)進(jìn)行運(yùn)行調(diào)試，觀察運(yùn)行結(jié)果是否到達(dá)預(yù)期的目的，運(yùn)行中可能出現(xiàn)邏輯錯誤，輸入數(shù)據(jù)適宜與否以及相關(guān)細(xì)節(jié)都可能會影響程序的運(yùn)行，可以試著變換