資源簡介

中小學教育資源及組卷應用平臺
第四單元練習題及參考答案
1.假設有一個八位二進制編碼，通過圖4-13所示二叉樹的后序遍歷可以得到該二進制編碼，請寫出該編碼。
參考答案：
01000110
分析：
后序遍歷是先訪問左子樹，再訪問右子樹，最后訪問根節點（對于子樹也采用此規則遍歷）。對上述二叉樹進行后序遍歷的過程如下圖所示。
2.已知算術表達式8-(6-4)*2+5,構建并畫出表達式二叉樹，將該算術表達式轉換成前綴表達式，嘗試利用前綴表達式完成計算。
參考答案：
表達式二叉樹如下圖所示。
前綴表達式：＋－8＊－６４２５
前綴表達式的計算過程如下所示：
＋－8＊－６４２５
　　　＊２２
　－８４
＋４５
９
分析：
對表達式二叉樹進行先序遍歷可以得到前綴表達式。對上圖所示二叉樹的先序遍歷過程，如下圖所示，對應的前綴表達式為＋－8＊－６４２５。
3.在先序遍歷序列中添加空子樹，標記后可以唯一確定二叉樹。已知某二叉樹帶標記的先序序列為：ABD EF C 手，畫出該二叉樹，并寫出它的中序遍歷和后序遍歷序列。
參考答案：
表達式二叉樹如下圖所示。
中序遍歷序列：ＤＢＦＥＣＧＡ
后序遍歷序列：ＤＦＧＣＥＢＡ
分析：
對上圖所示二叉樹的中序遍歷和后序遍歷過程如下圖所示。
　　　
　　　　　　中序遍歷　　　　　　　　　　　　　　　　后序遍歷
21世紀教育網 www.21cnjy.com 精品試卷·第 2 頁 （共 2 頁）
HYPERLINK "http://21世紀教育網(www.21cnjy.com)
" 21世紀教育網(www.21cnjy.com)

展開更多......

收起↑