計算機科學與技術課程設計

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

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

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

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

5、PR 均為空樹.由于刪去葉子結點不破壞整棵樹的結構,則只需要修改其雙親,結構點的指針即可.(2).若*parent 結點凡有左子樹 PL 或者只有右子樹 PR,此時只要令 PL 或 PR 直接成為其雙親結點*f 的左子樹即可.顯然,作此修改也不破壞二叉排序樹的特性.(3).若*parent 結點的左子樹均不空,并且注意二叉樹的平衡性,時刻調整.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,%