小型軟體系統開發技術文件
1.需求分析：
1.1 軟體的名稱：二叉樹輔助教學軟體
1.2 軟體的開發環境：在turbo c 2.0完整目錄下進行開發
1.3 軟體的目的：輔助教學
1.4 軟體面向的人群：在校教師或相關專業學生
1.5 軟體的功能：
a) 能夠根據資料檔案建立任意二叉樹；
b) 能夠演示遍歷（先序、中序、後序）過程；
c) 能夠演示線索化（先序、中序、後序）過程；
d) 能夠演示任意結點查詢過程；
e) 能夠演示葉子結點；
f) 能夠演示插入結點過程；
g) 能夠演示刪除子樹過程；
h) 能夠演示求樹高；
1.6 軟體的要求：
a) 軟體功能完整。
b) 軟體操作簡單，使用方便。
c) 軟體各個介面和功能的圖形演示清晰明了，文字區域、圖形區域設定合理。
d) 能夠獨立執行，不依賴環境。
2.術語定義：
2.1 二叉樹：每個結點最多有兩個子樹的有序樹。
通常子樹的跟被稱作「左子樹」和「右子樹」。這是乙個遞迴概念，在二叉樹的定義中用到二叉樹的概念。二叉樹有5中基本的形態：
2.2 遞迴:是指函式的定義中使用函式自身的方法。在一些程式語言，遞迴是進行迴圈的一種方法。
2.3 結點：二叉樹的元素也稱結點。
2.4 葉子：度為0的結點。
2.5 結點的度：結點所擁有的子樹的數目，二叉樹的結點度數最大為2.
2.6 父親（或雙親）：乙個結點稱為它的子樹的根的父親。
2.7 層：一顆二叉樹的根節點所在的層次為1，其他結點所在的層次等於它的雙親結點所在的層次加1.
2.8 深度：二叉樹葉子結點的最大層數。
2.9 遍歷：是指沿著某條搜尋路線，使得每個結點均被訪問一次且僅被訪問一次。
2.10 先序遍歷：
a) 訪問根結點；
b) 先序遍歷根結點的左子樹；
c) 先序遍歷根結點的右子樹。
2.11 中序遍歷：
d) 中序遍歷根節點左子樹；
e) 訪問根結點；
f) 中序遍歷根結點的右子樹。
2.12 後序遍歷
g) 後序遍歷根結點的左子樹；
h) 後序遍歷根結點的右子樹；
i) 訪問根結點
2.13 插入結點：如果要插入的該結點的左右子樹都不為空，則不能插入。
如果插入的該結點的左孩子，並且該結點左孩子為空，則插入該結點，否則不能插入該結點。如果插入的該結點的右孩子，並且該結點右孩子為空，則插入該結點，否則不能插入該結點。
2.14 刪除子樹：如果要刪除該結點，則把以該結點為跟的子樹也要刪除。
2.15 線索化二叉樹：為了方便地求出某一結點的前驅和後繼， 原有的二叉樹結構中，增加兩個鏈域：
plink和nlink，分別指向結點的任意結點在任意一次遍歷時得到的前驅和後繼。
3.軟體設計：
3.1 **設計：結構和資料組織方式葉子結點的顏色等
a) **具有系統性。**設計有規律，邏輯性強。首先設計這個軟體的資料結構，然後實現二叉樹的基本操作，再者實現二叉樹的演示，最後設計軟體的介面。
b) **要盡量簡潔。抽取函式的共性。
在查詢，插入，刪除的過程中都有用到查詢結點是函式，將其抽取出來作為共性。
在畫二叉樹的各個過程中，用到畫結點的函式，將其抽取出來，作為函式指標傳入其他函式中。
c) **具有可擴充性。使用了結構體來存放二叉樹結點的一些屬性，比如資料，位置等。這樣對於新增屬性來說很方便，比如後來演示的過程中用到行高標識，這樣直接新增上即可。
3.2 人機介面的設計：
a) 介面很簡單，只把軟體擁有的功能和提示資訊顯示出來。
b) 要便於操作和學習，有幫助功能。為了便於操作，我選擇輸入數字的方式來接受命令，因為功能也沒有幾個，所以選擇輸入數字來執行命令，還是很可取的方式。為了防止使用者輸入過程中輸入數字以外的鍵，在輸入錯誤的時候會有提醒。
並且會把數字對應的命令，顯示給使用者。
c) 能及時反饋錯誤資訊。在使用者輸入查詢，插入和刪除的資訊的時候，如果使用者輸入的不是合法是字元，會提示使用者重新輸入，直到使用者輸入的是合法的字元。
3.3 顯示的設計：
a) 在顯示的過程中，螢幕的上方還有下方都有相應的提示來進行提示該如何操作。
b) 結點的顯示方式，使用圓來代替結點，在圓心處顯示該結點的資料。
c) 整棵樹的顯示：
對於結點的顯示，我選擇用青色來填充，資料的顯示，我選擇紅色，樹枝的顯示，我選擇紅色來畫線。再加上背景是黑色，顯示出來很乾淨，漂亮。
d) 葉子結點是顯示:我選擇將顏色變為黃色的方式，來顯示這些是葉子。
e) 行高的顯示:首先我展示怎樣求得行高的過程（如果左右子樹行高相等，預設選擇左子樹），然後把得到行高的那幾個結點顯示出來。
f) 查詢結點的顯示:如果找到該結點，則該結點改變顏色，並在二叉樹的左下方顯示提示資訊，查詢到該結點。如果沒有找到該結點，結該結點不存在，則沒有葉子變色，在二叉樹的左下方顯示提示資訊沒有找到該結點。
g) 插入和刪除的顯示在：
首先查詢該結點是否存在，如果存在該結點，在進行相應的操作。
在查詢和刪除的過程中，如果不能插入和刪除會提示相應的資訊。
4.問題及解決方案總結：
4.1 如何顯示二叉樹問題：
解決方案： 在擴充套件先序建立二叉樹的時候就把每個結點的位置確定下來。
4.2 使用空指標問題：
這個問題還沒有解決，一直在查詢其存在的原因。
4.3 線索化的設計：（其他功能夠實現，只差線索化）
解決方案：
a) 重新構造資料結構，給每個結點加上左右標識位。
b) 沒有線索化，只是在遍歷的過程中查詢到該節點的前驅和後繼，然後把左子樹為空的指向其前驅，右子樹為空的指向其後繼。目的是達到演示線索化的結果。
c) 每個結點加上標識位，只是**索化的時候使用標識位，一旦線索化完成，將那些標識位為1的，再將其左右孩子置為空。這樣其他功能就不用更改。
d) 每個結點增加兩個指標域：plink和nlink來指向前驅和後繼，這樣既可以輕鬆線索化，其他函式又不用更改。
所以最後我選擇了d方案。
5.軟體使用說明：
1)在c盤下建立
2)執行環境：xp且支援c語言圖形環境。
3)cmd下執行
功能執行介面：
介面上有提示和要執行的命令，輸入相應的數字來執行。
0——回退按鍵
按下後進入上乙個操作介面，每個介面都攜帶此按鍵提示，若在主介面按它，退出
注意：以下鍵是在二叉樹不為空時，才會提示使用的鍵
1---顯示二叉樹
2——遍歷
按鍵後將提示：0——回退鍵；1——先序遍歷按鍵；2——中序遍歷按鍵；3——後序遍歷按鍵，再次按鍵（1或2或3）後，將進入遍歷提示介面，按後開始遍歷。
3——線索化
按鍵後將提示：：0——回退鍵；1——先序遍歷線索化按鍵；2——中序遍歷線索化按鍵；3——後序遍歷線索化按鍵，再次按鍵（1或2或3）後，將進入遍歷提示介面，按後開始遍歷。
4——查詢
按鍵後提示：輸入非法還是正確，如果正確則進行查詢，不正確則繼續輸入。 輸入正確後等待2s，然後開始查詢結點，若查詢成功，提示找到該結點，如果沒有查詢到，提示該結點不存在。
5——顯示葉子結點
6——插入
按鍵後提示輸入需要插入到哪個元素以及要插入的是左孩子還是右孩子，最後輸入要插入的值。如果條件符合，提示插入成功，否則插入失敗。
7——刪除
按鍵後提示輸入需要刪除的元素的和該元素的位置，輸入正確後，等待2s，然後開始以此結點為根結點進行結點閃爍的先序遍歷，緊接著提示開始刪除，並將刪除後得到的新的二叉樹顯示出來。
8——求樹高
按鍵後，閃爍結點表示進行樹高的計算，然後在二叉樹下方板塊顯示樹高。
僅供參考………………
二叉樹遍歷技巧
二叉樹先根序 後根序 中根序遍歷的速演算法 解題技巧 經過研究我找出了一種不用畫圖，由先 後 根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差，用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...
3最優二叉樹
計算機演算法的設計與分析實驗報告 1 描述 在權為wl，w2，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小 即代價最小 的二叉樹稱為最優二叉樹或哈夫曼樹。例 給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹 還有許多棵 它們的帶權路徑長度分別為 a wpl ...
二叉樹的遍歷
飛機票訂票系統 二 一四年六月 二叉數的遍歷 1 問題陳述 二叉樹的中序 前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。限1 人完成 二叉樹的前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。先序遍歷二叉樹演算法 若二叉樹為...