《廣工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告平衡二叉樹.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《廣工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告平衡二叉樹.doc（27頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 題目：平衡二叉樹學(xué) 院 專 業(yè) 年級(jí)班別 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 2015年7月1日1. 題目:采用字符類型為整型類型和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，實(shí)現(xiàn)抽象數(shù)據(jù)類型BTree。 ADT BTree 數(shù)據(jù)對(duì)象：Dai | aiElemSet， i=1,2,。,n, n0 數(shù)據(jù)關(guān)系：R1 ai1, aiD， i=2,.。,n 基本操作: Adj_balance(T） 操作結(jié)果：創(chuàng)建平衡二叉樹。 InsertAVL(T,search，taller) 初始條件：二叉樹T已存在。 操作結(jié)果：增加新結(jié)點(diǎn)。 SetAVL(T,search，taller） 初始條件：二叉樹T已存在. 操作結(jié)果:在平

2、衡二叉樹上增加新結(jié)點(diǎn)并調(diào)平衡。 DeleteAVL(T，search，shorter) 初始條件：二叉樹T已存在. 操作結(jié)果：刪除結(jié)點(diǎn)。 ADT BTree2 存儲(chǔ)結(jié)構(gòu)定義 公用頭文件DS0。h: #includestdio.h #include 樹的內(nèi)部變量 typedefstructBTNode int data;intbf;/平衡因子structBTNodelchild,rchild;/左、右孩子 BTNode,*BTree; /*需要的函數(shù)聲明/ voidRight_Balance(BTree&p)； voidLeft_Balance（BTreep）； voidLeft_Root_Ba

3、lance（BTree&T）； voidRight_Root_Balance（BTree&T)； boolInsertAVL（BTree&T，inti，bool&taller); voidPrintBT（BTreeT）; voidLeft_Root_Balance_det（BTreep，intshorter）； voidRight_Root_Balance_det（BTreep，intshorter）； void Delete(BTree q,BTree &r,int &shorter）; intDeleteAVL(BTreep,intx,intshorter)； voidAdj_balanc

4、e(BTreeT）; boolSetAVL（BTreeT,inti,booltaller)； boolInsert_Balance_AVL（BTreeT,inti，booltaller）; int menu（ )；3. 算法設(shè)計(jì) /*對(duì)以p為根的二叉排序樹作右旋處理/void Right_Balance(BTree p) BTree lc; lc =plchild； /lc指向的p左子樹根結(jié)點(diǎn) plchild = lcrchild； /rc的右子樹掛接為*p的左子樹 lcrchild = p; p = lc； /p指向新的結(jié)點(diǎn)/對(duì)以*p為根的二叉排序樹作左旋處理*/void Left_Bala

5、nce(BTree p) BTree rc； rc = prchild; /指向的p右子樹根結(jié)點(diǎn) p-rchild = rclchild; /rc左子樹掛接到p的右子樹 rclchild = p; p = rc； /p指向新的結(jié)點(diǎn)/*對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理/void Left_Root_Balance(BTree &T） BTree lc,rd； lc = T-lchild； /指向*T的左子樹根結(jié)點(diǎn) switch（lc-bf) /檢查T的左子樹的平衡度,并作相應(yīng)平衡處理 case 1： /新結(jié)點(diǎn)插入在T的左孩子的左子樹上，要作單右旋處理 Tbf = lcbf = 0；

6、 Right_Balance（T)； break; case 1： /新結(jié)點(diǎn)插入在*T的左孩子的右子樹上，要作雙旋處理 rd = lcrchild； /rd指向*T的左孩子的右子樹根 switch（rdbf） /修改*T及其左孩子的平衡因子 case 1: T-bf = 1； lcbf = 0； break; case 0： T-bf = lc-bf = 0; break; case 1： T-bf = 0; lcbf = 1; break; rdbf = 0； Left_Balance（Tlchild）; /對(duì)*T的左子樹作左旋平衡處理 Right_Balance(T); /對(duì)*T作右旋平衡

7、處理 /*對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理*/void Right_Root_Balance(BTree &T) BTree rc，ld； rc = Trchild； /指向T的左子樹根結(jié)點(diǎn) switch(rcbf） /檢查*T的右子樹的平衡度,并作相應(yīng)平衡處理 case -1: /新結(jié)點(diǎn)插入在T的右孩子的右子樹上，要作單左旋處理 Tbf = rcbf =0； Left_Balance（T); break; case 1： /新結(jié)點(diǎn)插入在*T的右孩子的左子樹上，要作雙旋處理 ld = rc-lchild; /ld指向T的右孩子的左子樹根 switch(ld-bf) /修改*T及其

8、右孩子的平衡因子 case 1： T-bf = 0; rcbf = 1； break； case 0: Tbf = rc-bf =0； break； case -1： T-bf = 1； rcbf = 0; break; ld-bf = 0； Right_Balance(T-rchild)；/對(duì)T的右子樹作左旋平衡處理 Left_Balance(T）； /對(duì)*T作左旋平衡處理 /插入結(jié)點(diǎn)i，若T中存在和i相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為i的新結(jié)點(diǎn)，并返回，否則返回*/bool InsertAVL（BTree &T,int i,bool &taller） if（！T)/插入新結(jié)點(diǎn)，樹“長(zhǎng)高

9、，置taller為true T = （BTree）malloc（sizeof（BTNode）)； T-data = i； T-lchild = T-rchild =NULL； T-bf = 0; taller = true; else if(i=T-data) /樹中已存在和有相同關(guān)鍵字的結(jié)點(diǎn) taller = 0； printf(已存在相同關(guān)鍵字的結(jié)點(diǎn)n”）； return 0; if（iTdata) /應(yīng)繼續(xù)在T的左子樹中進(jìn)行搜索 if（！InsertAVL(T-lchild,i,taller) return 0; else /應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 if（!InsertAVL（Trchild,i,taller)） return 0； return 1；/輸出二叉樹/void PrintBT（BTree T) if（T） printf（”%d”，Tdata)； if(Tlchild|T-rchild） printf（”(”）； PrintBT（T-lchild）； printf(,); PrintBT（Trchild)； printf(）; /刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理/void Left_Root_Balance_det(BTree p，int shorter） BTree p1，p2; if(p-bf=1） /p結(jié)點(diǎn)的左子樹高，刪除結(jié)