數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹(shù)調(diào)整為平衡二叉樹(shù)(已修改)
2025-06-19 14:48 本頁(yè)面
【正文】 學(xué)號(hào) 1208020228 《 數(shù)據(jù)結(jié)構(gòu) 》課程設(shè)計(jì)報(bào)告 題目： 二叉排序樹(shù)調(diào)整為平衡二叉樹(shù) 專業(yè)： 網(wǎng)絡(luò)工程 班級(jí)： 二 姓名： 汪杰 指導(dǎo)教師： 劉義紅 成績(jī)： 計(jì)算機(jī)與信息工程系 2021年 1 月 2 日 20212021 學(xué)年 第 一 學(xué)期 計(jì)算機(jī)與信息工程系 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告 1 目錄 問(wèn)題描述 ??????????????? 設(shè)計(jì)思路 (數(shù)學(xué)模型的選擇 ) ????? 二叉排序樹(shù)和平衡二叉樹(shù) 定義 ?????????? 程序清單 ??????????? ??????????? ????????? ????????????? 計(jì)算機(jī)與信息工程系 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告 1 輸入帶排序序列生成二叉排序樹(shù)，并調(diào)整使其變?yōu)槠胶舛鏄?shù) ，運(yùn)行并進(jìn)行調(diào)試。 平衡二叉樹(shù)的調(diào)整方法 平衡二叉樹(shù)是在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹(shù)的平衡性，若是，則找出其中的最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。具體步驟如下： ⑴ 每當(dāng)插入一個(gè)新結(jié)點(diǎn)，從該結(jié)點(diǎn)開(kāi)始向上計(jì)算各結(jié)點(diǎn)的平衡因 子，即計(jì)算該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子，若該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值均不超過(guò) 1，則平衡二叉樹(shù)沒(méi)有失去平衡，繼續(xù)插入結(jié)點(diǎn)； ⑵ 若插入結(jié)點(diǎn)的某祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值大于 1，則找出其中最小不平衡子樹(shù)的根結(jié)點(diǎn)； ⑶ 判斷新插入的結(jié)點(diǎn)與最小不平衡子樹(shù)的根結(jié)點(diǎn)的關(guān)系，確定是哪種類型的調(diào)整； ⑷ 如果是 LL 型或 RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過(guò)程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是 LR型或 LR 型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹(shù)的根結(jié)點(diǎn)先不動(dòng)，調(diào)整插入結(jié)點(diǎn)所在子樹(shù)，第二次再計(jì)算機(jī)與信息工程系 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1