石河子大學
資訊科學與技術學院
資料結構課程設計報告
完成日期：2010-03
目錄1.課程設計的思路及涉及的知識點………………………1
2.需求分析1
3.程式的主要功能及模組設計與分析……………………2
4.課程設計的原程式6
5.程式的除錯分析17
6.收穫及體會21
7.參考書籍21
1.設計思路及涉及的知識點
本程式名為二叉排序樹的應用，即是對二叉排序樹做相應的操作，如建樹，遞增、遞減輸出等。設計用鍊錶完成，如此就要建立帶指標的結點，完成相應的操作。
1.1本系統設計的思路:
運用鍊錶所特有的動態開闢分配刪除記憶體的特點，可以完成結點動態建立，形成一棵排序樹。再通過鍊錶中結點之間的連線，進行相應的操作，如算平均查詢長度等。
但是在使用鍊錶的指針對資料進行操作中，首位結點的妥善處理是很細微的，也是很關鍵與相對煩瑣的，對與鍊錶的頭結點的使用一般避免不了，但是我們在鍊錶的迴圈中可以通過鍊錶中結點數來控制開始與停止，這樣可以避免鍊錶尾結點next帶來的不便。這樣便要求我們每時每刻都要得到鍊錶中結點數的準確值，對於這我們可以通過全域性變數來解決。
與此同時為了資料的儲存，在每次更改資料記錄時便提示使用者用新的資料替代舊的，用文件可以完成此操作，當然可以不替代。在完成一次操作後，我們將資料儲存到文件中，結點數同樣儲存到文件中，這樣想儲存的資料便不會丟了，而且每次從新啟動系統都可以得到上次的資訊記錄，結點數，這些與文件有關的操作要用到檔案流操作，同時由於資料是以結點為元素的，這就暗示我們用二進位制檔案進行操作，為了方便檢驗系統的正誤性，特設了asiic碼檔案。
1.2涉及的知識點：
二叉排序樹及查詢過程；
二叉排序樹的插入和刪除；
二叉排序樹的查詢分析；
平衡因子的概念；
2.需求分析：
3.1輸入數列l建立一棵二叉排序樹t；
3.2對二叉排序樹做遞增、遞減輸出；
3.3求二叉排序樹的平均查詢長度；
3.4刪除二叉排序樹上的指定結點；
3.5輸出二叉排序樹中指定結點的平衡因子；
3.程式的主要功能及模組設計
3.1．程式的主要功能
3.2 模組的功能、設計與分析
3.2.1建立bst：
我所用的建立方法是用sort函式對輸入的每個結點進行排序，即輸入的每個結點與第乙個進行比較比根結點大的放在右邊，比它小的放在左邊，依次以每個結點為根節點再進行比較即可。輸出得到二叉排序樹。
3.2.2先序遍歷bst即遞增輸出二叉樹用遞迴演算法呼叫函式依次輸出左根右結點。
3.2.3對bst做遞減輸出同樣用遞迴演算法輸出結點依次為右根左。
4.2.4計算平均查詢長度：在程式開始時定義過三個全域性變數n,m,total,在先序遍歷函式中用n記住每個結點，在asl函式中用total/n 得出平均查詢長度，輸出得出。
3.2.5用後序遍歷函式找到要求的結點，在分別求出左右子樹的深度返回樹的深度，在求平衡因子的函式中定義兩個變數m1,m2分別把左右子樹的深度存入其中，兩個相減即為該結點的平衡因子。
3.3.主要流程圖
3.3.1建立bst:
3.3.2中序遍歷二叉排序樹：
3.3.3後序遍歷查詢：
3.3.4刪除指定結點：
4.課程設計的原程式
#include <>
#include <>
#include <>
#define null 0
#define ok 1
#define error 0
#define maxsize 100
typedef struct node
btnode;
int n,m,total;
程式的介面
void menu()
將c插入到二叉排序樹t中
void sort(btnode *t,int c)
else sort(t->right,c);
if(cdata)
if(t->left==null)
else sort(t->left,c);
}建立二叉排序樹
btnode *creat()
return ht;
}對二叉排序樹做遞增輸出
void inorder(btnode *t)
}對二叉排序樹做遞減輸出
void destorder(btnode *t)
}計算二叉排序樹的平均查詢長度********/
void asl()
查詢指定的結點
二叉排序樹
目錄摘要 前言 正文 1 1.採用類c語言定義相關的資料型別 1 2.各模組的偽碼演算法 2 3.函式的呼叫關係圖 6 4.除錯分析 7 5.測試結果 8 6.源程式 帶注釋 15 總結 19 參考文獻 20 致謝 25 附件 部分源程式 26 該設計要求對二叉樹排序問題進行解決。可按輸入二叉樹 增...
二叉排序樹C 實現
include using namespace std class bisorttree 二叉樹結點類的定義 class binode 二叉排序樹類定義 class bisorttree private binode root binode search binode root,int key vo...
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...