用順序和二叉鏈表作存儲結(jié)構(gòu)實(shí)現(xiàn)二叉排序樹全代碼.doc

數(shù)學(xué)與計(jì)算機(jī)學(xué)院 課程設(shè)計(jì)說明書 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課 程 代 碼 6013799 題 目 二叉排序樹的實(shí)現(xiàn) 年級 專業(yè) 班 10 級計(jì)科 3 班 學(xué) 生 姓 名 學(xué) 號 開 始 時(shí) 間 2012 年 12 月 25 日 完 成 時(shí) 間 2013 年 01 月 8 日 課程設(shè)計(jì)成績 學(xué)習(xí)態(tài)度及平 時(shí)成績 30 技術(shù)水平與實(shí)際 能力 20 創(chuàng)新 5 說明書撰寫質(zhì)量 45 總 分 100 指導(dǎo)教師簽名 年 月 日 二叉排序樹的實(shí)現(xiàn) 目 錄 1 1 引引 言言 1 1 1 問題的提出 1 1 2 任務(wù)與分析 1 2 2 程序的主要功能程序的主要功能 2 2 1 二叉排序樹的建立 2 2 2 二叉排序樹的中序遍歷 2 2 3 二叉排序樹中元素的查找 2 2 4 二叉排序樹中元素的刪除 3 3 3 程序運(yùn)行平臺程序運(yùn)行平臺 4 4 4 總體設(shè)計(jì)總體設(shè)計(jì) 5 5 5 程序類的說明程序類的說明 6 6 6 模塊模塊 9 6 1 中序遍歷模塊 9 6 2 刪除模塊 9 7 7 系統(tǒng)測試系統(tǒng)測試 12 7 1 順序存儲 12 7 2 二叉鏈表存儲 16 8 8 結(jié)論結(jié)論 19 總 結(jié) 19 心得體會 20 參考文獻(xiàn)參考文獻(xiàn) 21 全部代碼全部代碼 22 二叉鏈表結(jié)構(gòu)C 22 二叉鏈表結(jié)構(gòu)C 26 順序存儲結(jié)構(gòu)C 29 二叉排序樹的實(shí)現(xiàn) 摘摘 要要 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之 間的關(guān)系和操作等的學(xué)科 本課程設(shè)計(jì)中的二叉排序樹 可以用順序存儲和鏈?zhǔn)酱鎯?兩種算法計(jì)算 本課程設(shè)中的二叉排序樹 一共要實(shí)現(xiàn)四項(xiàng)基本的功能 它們分別是 二叉搜索樹的創(chuàng)建 中序遍歷 查找結(jié)點(diǎn)和刪除結(jié)點(diǎn) 關(guān)鍵詞 二叉排序樹 中序遍歷 搜索結(jié)點(diǎn) 刪除結(jié)點(diǎn) C C 1 二叉排序樹的實(shí)現(xiàn) 1 引 言 1 1 問題的提出 研究關(guān)于如何創(chuàng)建二叉排序樹并對樹進(jìn)行遍歷 查找和刪除等操作 同時(shí)關(guān)注用 順序和二叉鏈表作存儲結(jié)構(gòu)帶來的區(qū)別 1 2 任務(wù)與分析 用順序和二叉鏈表作存儲結(jié)構(gòu)實(shí)現(xiàn)二叉排序樹 1 以回車 n 為輸入結(jié)束標(biāo)志 輸入數(shù)列 L 生成一棵二叉排序樹 T 2 對二叉排序樹 T 作中序遍歷 輸出結(jié)果 3 輸入元素 x 查找二叉排序樹 T 若存在含 x 的結(jié)點(diǎn) 則刪除該結(jié)點(diǎn) 并作中序 遍歷 執(zhí)行操作 2 否則輸出信息 無 x 2 二叉排序樹的實(shí)現(xiàn) 2 程序的主要功能 2 1 二叉排序樹的建立 建二叉樹的結(jié)點(diǎn)至少應(yīng)當(dāng)包含三個(gè)域 分別存放結(jié)點(diǎn)的數(shù)據(jù) data 左子女結(jié)點(diǎn)指 針 leftChild 和右子女結(jié)點(diǎn)指針 rightChild 整個(gè)二叉樹的鏈表要有一個(gè)表頭指針 它指 向二叉樹的根結(jié)點(diǎn) 其作用是當(dāng)作樹的訪問點(diǎn) 從空的二叉排序樹開始 經(jīng)過一系列的查找插入操作以后 生成了一棵二叉排序 樹 根據(jù)二叉排序樹的定義 建立一棵二叉排序樹的過程是按照待排序序列元素的先 后次序 不斷動(dòng)態(tài)生成二叉樹的結(jié)點(diǎn) 逐個(gè)插入到二叉樹中 若 p 為根結(jié)點(diǎn)指針 b 為 當(dāng)前待插入元素 其過程可以描述為 若為空樹 p nil 動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn) 其數(shù)據(jù)域?yàn)楫?dāng)前待插入元素 b 左 右指 針域?yàn)?空 p 指向該結(jié)點(diǎn) 若非空樹 比較 b 與根結(jié)點(diǎn)數(shù)據(jù) data p 如果 bdata p t return 1 else if keydata searchBST t lchild key t p else searchBST t rchild key t p insertBSTinsertBST 的聲明的聲明 insertBST node t int key node p NULL s NULL if searchBST t key NULL s data key s lchild s rchild NULL if p t s else 7 二叉排序樹的實(shí)現(xiàn) if keydata p lchild s else p rchild s return 1 else return 0 inorderTraverseinorderTraverse 類的聲明類的聲明 inorderTraverse node t if t if inorderTraverse if inorderTraverse return 1 DeleteDelete 類的聲明類的聲明 node Delete node t int key node p t q NULL s f while p NULL if p data key break q p if p data key p p lchild else p p rchild if p NULL return t if p lchild NULL 8 二叉排序樹的實(shí)現(xiàn) if q NULL t p rchild else if q lchild p q lchild p rchild else q rchild p rchild free p else f p s p lchild while s rchild f s s s rchild if f p f lchild s lchild else f rchild s lchild p data s data free s return t 9 二叉排序樹的實(shí)現(xiàn) 6 模塊 6 1 中序遍歷模塊 系統(tǒng)將提示用戶輸入新添加的數(shù)據(jù) 輸入結(jié)束后進(jìn)行中序遍歷 關(guān)鍵代碼 inorderTraverse node t 中序遍歷函數(shù) if t if inorderTraverse 輸出根結(jié)點(diǎn) if inorderTraverse 中序遍歷根的右子 樹 return 1 6 2 刪除模塊 系統(tǒng)將對用戶輸入的數(shù)進(jìn)行查找 查找到之后刪除此數(shù) 并對全部數(shù)據(jù)進(jìn)行中序遍歷 關(guān)鍵代碼 node Delete node t int key 刪除函數(shù) node p t q NULL s f while p NULL 查找要?jiǎng)h除的點(diǎn) 10 二叉排序樹的實(shí)現(xiàn) if p data key break q p if p data key p p lchild else p p rchild if p NULL return t 查找失敗 if p lchild NULL p 指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn) if q NULL t p rchild q 指向要?jiǎng)h結(jié)點(diǎn)的父母 else if q lchild p q lchild p rchild p 為 q 的左孩子 else q rchild p rchild p 為 q 的右孩子 free p else p 的左孩子不為空 f p s p lchild 11 二叉排序樹的實(shí)現(xiàn) while s rchild 左拐后向右走到底 f s s s rchild if f p f lchild s lchild 重接 f 的左子樹 else f rchild s lchild 重接 f 的右子樹 p data s data free s return t 12 二叉排序樹的實(shí)現(xiàn) 7 系統(tǒng)測試 首先進(jìn)入 VC 6 0 打開工程 zjr dsw 然后進(jìn)入源程序 也可以不打開工程 直 接雙擊 zjr 文件夾下的 zjr exe 文件即可運(yùn)行程序 7 1 順序存儲 圖 7 1 1 打開程序 成功顯示提示信息 13 二叉排序樹的實(shí)現(xiàn) 圖 7 1 2 輸入數(shù)據(jù) 以 0 結(jié)束輸入 操作成功 14 二叉排序樹的實(shí)現(xiàn) 圖 7 1 3 功能 1 中序輸出數(shù)據(jù) 操作成功 圖 7 1 4 功能 2 刪除數(shù)據(jù) 顯示提示信息 操作成功 15 二叉排序樹的實(shí)現(xiàn) 圖 7 1 5 刪除數(shù)據(jù) 操作成功 16 二叉排序樹的實(shí)現(xiàn) 圖 7 1 6 重復(fù)執(zhí)行程序 操作成功 7 2 二叉鏈表存儲 圖 7 2 1 打開程序 顯示提示信息 操作成功 17 二叉排序樹的實(shí)現(xiàn) 圖 7 2 2 功能 1 輸入數(shù)據(jù) 進(jìn)行中序遍歷 操作成功 18 二叉排序樹的實(shí)現(xiàn) 圖 7 2 3 功能 2 輸入數(shù)據(jù) 進(jìn)行刪除 操作失敗 因?yàn)闆]有此數(shù)據(jù) 顯示 錯(cuò)誤信息 圖 7 2 4 功能 2 輸入數(shù)據(jù) 進(jìn)行中序遍歷 操作成功 通過上述測試 本系統(tǒng)實(shí)現(xiàn)了二叉樹的生成 中序遍歷 查找刪除功能 能避免 數(shù)據(jù)的輸入錯(cuò)誤等 驗(yàn)證結(jié)果正確 說明其符合算法設(shè)計(jì)的要求 1 正確性 可讀性 健壯性 效率與低儲存量需求 要寫一個(gè)優(yōu)質(zhì)的算法 就必須考慮其時(shí)間復(fù)雜度 它表 示隨問題的規(guī)模 n 的增大 算法執(zhí)行時(shí)間的增長率和 f n 的增長率相同 和空間復(fù) 雜度 遍歷二叉樹的算法中的基本操作是訪問結(jié)點(diǎn) 則不論按哪一次次序進(jìn)行遍歷 對含 n 個(gè)結(jié)點(diǎn)的二叉樹 其時(shí)間復(fù)雜度都為 O n 所需空間為遍歷過程中棧的最大 容量 即樹的深度 最壞情況下為 n 則空間復(fù)雜度也為 O n 19 二叉排序樹的實(shí)現(xiàn) 8 結(jié)論 總 結(jié) 這次課程設(shè)計(jì)使我對數(shù)據(jù)結(jié)構(gòu)認(rèn)識深刻了許多 其中最深刻的是我理解了用二叉 鏈表結(jié)構(gòu)存儲實(shí)現(xiàn)二叉排序樹 同時(shí)也加深了對二叉樹的理解 本課程設(shè)計(jì)實(shí)現(xiàn)了二 叉排序樹的創(chuàng)建 中序遍歷 刪除二叉排序樹中某個(gè)結(jié)點(diǎn) 在進(jìn)行搜索時(shí) 還可以采 用更好的搜索結(jié)構(gòu)即動(dòng)態(tài)搜索結(jié)構(gòu) 當(dāng)沒有找到時(shí) 可以將其插入 而不是僅僅提示 未找到 通過這一次的課程設(shè)計(jì) 我已經(jīng)會用二叉鏈表存儲結(jié)構(gòu)實(shí)現(xiàn)對二叉排序樹的 的創(chuàng)建 中序遍歷 查找和某個(gè)刪除結(jié)點(diǎn)等基本操作 但我同時(shí)也發(fā)現(xiàn)了自己許多不足之處 首先 對數(shù)據(jù)結(jié)構(gòu)的掌握還不夠 雖然完成了程序 但是只用到了基本的結(jié)點(diǎn)以 及鏈表 在數(shù)據(jù)結(jié)構(gòu)的選擇上避重就輕 覆蓋面較小 不能很好的體現(xiàn)各種數(shù)據(jù)結(jié)構(gòu) 的掌握度 同時(shí)也缺少了適當(dāng)?shù)腻憻?在這方面還需要自己主動(dòng)去提高 其次 在程序整體的設(shè)計(jì)上還不夠完善 各模塊可以適當(dāng)增加內(nèi)容 界面還可以 更加的人性化些 這樣整個(gè)程序才具有更強(qiáng)的美觀性與實(shí)用性 總而言之 這次課程 設(shè)計(jì)給了我很大啟發(fā) 我明白了 不管遇到什么問題 只要抓住根源 不氣餒 從不 同方面去攻破它 終究會成功 生活也是如此 在今后的工作 學(xué)習(xí)中我將認(rèn)真總結(jié) 經(jīng)驗(yàn)教訓(xùn) 努力使自己成為一名技術(shù)過硬 工作嚴(yán)謹(jǐn) 思維活躍的工程人員 為提高 人們的生活質(zhì)量做出更大的貢獻(xiàn) 20 二叉排序樹的實(shí)現(xiàn) 心得體會 課程設(shè)計(jì)結(jié)束了 在這次的課程設(shè)計(jì)中不僅檢驗(yàn)了我所學(xué)的知識 也培養(yǎng)了我如 何去把握一件事情 如何去做一件事情 課程設(shè)計(jì)是我們專業(yè)課程知識綜合應(yīng)用的實(shí) 踐訓(xùn)練是我們邁向社會 從事職業(yè)工作前一個(gè)必不可少的過程 我這次設(shè)計(jì)的科目是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問 題中計(jì)算機(jī)的操作對象 數(shù)據(jù)元素 以及它們之間的關(guān)系和運(yùn)算等的學(xué)科 而且確保 經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型 這次通過對二叉排序樹的深 入研究 我又一次的溫習(xí)了 c c 和數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識 盡管這中間經(jīng)歷好多困難 但我通過查找多種資料 利用網(wǎng)絡(luò)優(yōu)勢 完成了任務(wù) 我這次課程設(shè)計(jì)代碼中主要使用了鏈表的循環(huán)和遍歷這兩種操作 循環(huán)鏈表是單 鏈表的另一種形式 遍歷是指沿著某條收索路線 依次對樹中每個(gè)節(jié)點(diǎn)均作一次且僅 作一次訪問 通過這次的課程設(shè)計(jì) 更是讓我深刻認(rèn)識到自己在學(xué)習(xí)中的不足 同時(shí) 也找到了克服這些不足的方法 這是一筆很大的資源 在以后的學(xué)習(xí)中 我們應(yīng)該利 用更多的時(shí)間去上機(jī)實(shí)驗(yàn) 加強(qiáng)自學(xué)的能力 多編寫程序 相信不久以后我們的編程 能力都會有很大的提高 能創(chuàng)作出更多更完善更有新意的作品出來 21 二叉排序樹的實(shí)現(xiàn) 參考文獻(xiàn) 1 譚浩強(qiáng) 編著 程序設(shè)計(jì) 北京 清華大學(xué)出版社 2000 2 王珊珊 張志航 編著 C 程序設(shè)計(jì)教程 北京 機(jī)械工業(yè)出版社 2011 3 嚴(yán)蔚敏 吳偉民 編著 數(shù)據(jù)結(jié)構(gòu) 北京 清華大學(xué)出版社 2001 22 二叉排序樹的實(shí)現(xiàn) 全部代碼全部代碼 二叉鏈表結(jié)構(gòu)二叉鏈表結(jié)構(gòu) c include include typedef struct Tnode int data 輸入的數(shù)據(jù) struct Tnode lchild rchild 結(jié)點(diǎn)的左右指針 分別指向結(jié)點(diǎn)的左右孩子 node BSTnode searchBST node t int key node f node p 查找函數(shù) if t p f return 0 查找不成功 else if key t data p t return 1 查找成功 else if keydata searchBST t lchild key t p 在左子樹中繼續(xù)查找 else searchBST t rchild key t p 在右子樹中繼續(xù)查找 insertBST node t int key 插入函數(shù) node p NULL s NULL if searchBST t key NULL s data key s lchild s rchild NULL if p t s 被插結(jié)點(diǎn) s 為新的根結(jié)點(diǎn) else if keydata p lchild s 被插結(jié)點(diǎn) s 為左孩子 else p rchild s 被插結(jié)點(diǎn) s 為右孩子 return 1 else return 0 樹中已有關(guān)鍵字相同的結(jié)點(diǎn) 不再插入 23 二叉排序樹的實(shí)現(xiàn) inorderTraverse node t 中序遍歷函數(shù) if t if inorderTraverse 輸出根結(jié)點(diǎn) if inorderTraverse 中序遍歷根的右子樹 return 1 node Delete node t int key 刪除函數(shù) node p t q NULL s f while p NULL 查找要?jiǎng)h除的點(diǎn) if p data key break q p if p data key p p lchild else p p rchild if p NULL return t 查找失敗 if p lchild NULL p 指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn) if q NULL t p rchild q 指向要?jiǎng)h結(jié)點(diǎn)的父母 else if q lchild p q lchild p rchild p 為 q 的左孩子 else q rchild p rchild p 為 q 的右孩子 free p else p 的左孩子不為空 f p s p lchild while s rchild 左拐后向右走到底 f s s s rchild if f p f lchild s lchild 重接 f 的左子樹 24 二叉排序樹的實(shí)現(xiàn) else f rchild s lchild 重接 f 的右子樹 p data s data free s return t void main node T NULL int num int s 0 j 0 i 0 int ch 0 node p NULL printf 輸入一串?dāng)?shù) 每個(gè)數(shù)以空格分開 do scanf d if num printf 完成輸入 n else insertBST while num printf n 1 中序輸出 printf n 2 輸入元素 while ch ch scanf d switch ch case 0 exit 0 0 退出 case 1 printf 中序遍歷輸出結(jié)果為 n inorderTraverse 1 中序遍歷 break case 2 printf 輸入元素 x 查找二叉排序樹 T 若存在含 x 的結(jié)點(diǎn) 則刪除該結(jié)點(diǎn) 并作中序遍歷 否則輸 出無 x scanf d 3 刪除某個(gè)結(jié)點(diǎn) if searchBST T num NULL 25 二叉排序樹的實(shí)現(xiàn) printf 刪除成功 中序遍歷輸出 n inorderTraverse else printf 無 d num break default printf 無此結(jié)點(diǎn) n break 輸入無效字符 26 二叉排序樹的實(shí)現(xiàn) 二叉鏈表結(jié)構(gòu)二叉鏈表結(jié)構(gòu) c include using namespace std class node public node int i data i left NULL right NULL void inorder node cout data right void insert node else if itemdata insert ptr left item else insert ptr right item node find node if ptr data item return ptr else if itemdata find ptr left item else find ptr right item node else if itemdata 27 二叉排序樹的實(shí)現(xiàn) findy ptr left item else findy ptr right item node rl return left node rr return right void dele node else if ptr rr NULL ptr ptr rl else ptr ptr rr private int data node left 左孩子結(jié)點(diǎn) node right 右孩子結(jié)點(diǎn) int main int t i 0 j cout t cout 輸入 t j node x new node j for i j x insert x j cout inorder x 作中序遍歷 cout n 輸入操作 當(dāng)輸入 1 時(shí)程序結(jié)束 j while j 1 node t x find x j 定位結(jié)點(diǎn) if t NULL 28 二叉排序樹的實(shí)現(xiàn) node x dele y cout inorder x else cout 無 j cout n 輸入操作 當(dāng)輸入 1 時(shí)程序結(jié)束 j return 0 29 二叉排序樹的實(shí)現(xiàn) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) c include stdio h include malloc h include windows h define endflag 999999 define N 1000 int b N typedef struct int data int other int flag1 Link void Build Link a N int w i j k for i 0 i N i a i flag1 0 a i data 0 printf n t t t 請輸入樹的根結(jié)點(diǎn) scanf d a 1 flag1 1 printf n t t t 請輸入結(jié)點(diǎn)個(gè)數(shù) scanf d for j 1 j k j printf n t t t 請輸入結(jié)點(diǎn)的數(shù)值 scanf d printf n t t t 第 d 位 d j w a 0 data w a 0 flag1 1 i 1 if a 0 data a i data loop if a 2 i flag1 0 30 二叉排序樹的實(shí)現(xiàn) a 2 i data a 0 data a 2 i flag1 a 0 flag1 if a 2 i flag1 1 i 2 i if a 0 dataa i data goto loop1 if a 0 data a i data loop1 if a 2 i 1 flag1 0 a 2 i 1 data a 0 data a 2 i 1 flag1 a 0 flag1 if a 2 i 1 flag1 1 i 2 i 1 if a 0 dataa i data goto loop1 void Sdel Link a N int i int flag 0 int q int number 1 int j 1 int b N printf n t t t 請輸入需要?jiǎng)h除的結(jié)點(diǎn)的數(shù)值 scanf d for i 1 i N i 31 二叉排序樹的實(shí)現(xiàn) if a i data q a i data 0 printf n t t t 已刪除 d q flag 1 for i 1 i