計算機科學與技術(shù)課程設(shè)計

1、計算機科學與技術(shù)系課程設(shè)計說明書第 1 頁共 20一、課程設(shè)計題目 一、課程設(shè)計題目二叉平衡排序樹 二叉平衡排序樹摘要 摘要 問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹轉(zhuǎn)換為二叉平衡排序樹?；疽螅?.創(chuàng)建（插入、調(diào)整、改組）2.輸出開發(fā)工具:windows XP 操作系統(tǒng),Microsoft visual c++ 6.0 編譯系統(tǒng);關(guān)鍵詞：C++ ;二、設(shè)

2、計主要目的及意義 二、設(shè)計主要目的及意義 目的 目的:1.熟悉掌握二叉樹的基本操作2.熟悉二叉樹的創(chuàng)建(插入、調(diào)整、改組),輸出以及把二叉排序樹轉(zhuǎn)換為二叉平衡排序樹3.更進一步掌握有關(guān)二叉排序樹的操作意義 意義:軟件課程設(shè)計是計算機科學與技術(shù)專業(yè)軟件方向的一個重要環(huán)節(jié)，是語言類課程學習的總結(jié)。通過課程設(shè)計使我們加深對程序設(shè)計的理解，掌握程序開發(fā)的基本方法，深化學生面向?qū)ο蟮木幊淘O(shè)計思想和新一代程序設(shè)計的邏輯思維方式，把課堂上所學到的多個

3、單元串到一起，提高我們在軟件設(shè)計過程中分析問題和解決問題的實際動手能力，使我們的理論知識和實踐技能得到共同發(fā)展，最終提高我們解決問題和分析問題的能力。為我們踏上工作崗位之前提供了一次專業(yè)研究和項目開發(fā)的寶貴實踐機會，為今后的工作積累經(jīng)驗。計算機科學與技術(shù)系課程設(shè)計說明書第 3 頁共 20當結(jié)點不存在時,將待插入到根結(jié)點的關(guān)鍵字 key 和樹根關(guān)鍵字 parent->key 進行比較.若 keykey,則插入到根的左子樹中,否則,插

4、入到根的右子樹中.而子樹中的插入過程和在樹中的插入過程相同,如此進行下去,直到把結(jié)點作為一個新的樹葉插入到二叉排序樹中或者直到發(fā)現(xiàn)樹已有相同關(guān)鍵字的結(jié)點為止,并且注意二叉樹的平衡,時刻調(diào)整.b.二叉排序樹的刪除假設(shè)在二叉排序樹上被刪結(jié)點為*tp,其雙親結(jié)點為*parent,且不失一般性,可設(shè)*parent 是*parent->left 的左孩子.下面分了 3 種情況進行討論:(1).若*parent 結(jié)點為葉子結(jié)點,即 PL 和

5、PR 均為空樹.由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu),則只需要修改其雙親,結(jié)構(gòu)點的指針即可.(2).若*parent 結(jié)點凡有左子樹 PL 或者只有右子樹 PR,此時只要令 PL 或 PR 直接成為其雙親結(jié)點*f 的左子樹即可.顯然,作此修改也不破壞二叉排序樹的特性.(3).若*parent 結(jié)點的左子樹均不空,并且注意二叉樹的平衡性,時刻調(diào)整.4.中序遍歷和先序遍歷 中序遍歷和先序遍歷Void interordertraverse(no

6、de* root)//中序遍歷{If(root 1=NULL){Interordertraverse(root->left);Printf(“%d,%d\n,“root->key,root->balance);Interordertraverse(root->right);}}Void preordertraverse (node* root)//先序遍歷{If (root!=NULL){Printf(“%d,%