基于雙向二叉樹的多級菜單設計及實現

曹陽

（重慶工商職業學院，重慶，401520）

0 引言

隨著電子技術的發展，電子設備的智能化水平不斷提高，電子設備的功能越來越復雜，需要顯示的數據也越來越多，單一的顯示界面已經不能滿足電子設備的顯示需求。多級菜單顯示可以將信息進行分類別、分層次、分屏幕的顯示，即能夠滿足多功能、多數據顯示的需求，又能實現電子設備顯示實時性要求，在智能電子設備中得到廣泛應用。

目前多級菜單系統多采用索引號串聯菜單的方式實現[1～3]。使用索引號串聯菜單在多級菜單設計及實現過程中涉及較多的數據結構和關鍵參數，當多級菜單系統升級或修改時，需要修改較多的數據結構和關鍵參數，增加軟件升級難度和工作量。基于此，本文設計并實現了一種基于雙向二叉樹的多級菜單系統，當多級菜單系統升級或變化時，只需重新獲取雙向二叉樹先序遍歷序列和中序遍歷序列即可完成多級菜單系統的升級，降低了系統升級難度和工作量。

1 基于雙向二叉樹的多級菜單模型

典型的多級菜單系統可以分為選擇型菜單和功能型菜單[8]，如圖1所示。選擇型菜單并不執行某項具體任務，而是用于選擇某項功能，如圖1中的A、B菜單。功能型菜單一般位于多級菜單的最底層，用于執行某項具體功能，如圖1中的C、D、E、F菜單。

圖1 多級菜單

多級菜單系統在結構上和數據結構中的非線性結構—樹型結構相似，是一種典型的多層次嵌套結構，多級菜單系統可以采用樹型結構表示。多級菜單可以直觀的轉化為樹型結構中的多叉樹，但是由于多叉樹中父節點的子節點數量是不確定的，存儲上難以采用統一的存儲結構表示，實現困難。二叉樹是一種常用的樹型結構，其特點是每個節點上至多有兩個子節點，且節點的左右順序不可以任意顛倒[11]。由于二叉樹節點的子節點數量是固定的，可以采用統一的存儲結構表示，且多叉樹可以轉換為相應的二叉樹，因此多級菜單系統可以采用二叉樹的結構表示和實現。

二叉樹的生成可以由其先序遍歷序列和中序遍歷序列確定，而與其生成算法無關。因此僅需修改二叉樹的先序遍歷序列和中序遍歷序列即可以重新生成新的二叉樹，以滿足多級菜單系統升級，降低了工作量和難度。

一般的二叉樹在設計上僅支持單向訪問，即父節點可以訪問子節點，子節點不可以訪問父節點。在多級菜單系統中，經常需要訪問后級菜單和返回前級菜單，以及同級菜單選項之間相互切換，普通的二叉樹無法實現多級菜單之間的相互訪問和切換。因此本文采用雙向二叉樹的方式實現多級菜單，父節點存儲前級菜單選項1的相關信息，左子節點存儲后級菜單信息，右子節點存儲前級菜單選項2信息，父節點與子節點之間可以相互訪問，以實現前級菜單，后級菜單及同級菜單多個選項之間的訪問和切換。雙向二叉樹結構如圖2所示。

圖2 雙向二叉樹

2 基于雙向二叉樹的多級菜單實現

基于雙向二叉樹的多級菜單通過二叉樹節點實現多級菜單之間的相互切換和訪問，雙向二叉樹的構造是實現節點之間訪問和切換的關鍵和基礎。雙向二叉樹構造的設計思路是首先將多級菜單轉換為雙向二叉樹；然后將各菜單需要顯示的信息進行映射和編碼，并將編碼值存儲于雙向二叉樹節點中，以編碼值表示各菜單顯示信息；最后根據多級菜單轉換的雙向二叉樹獲得雙向二叉樹的先序遍歷序列和中序遍歷序列，通過先序遍歷序列和中序遍歷序列利用遞歸構造算法構造雙向二叉樹。

2.1 多級菜單轉化雙向二叉樹

多級菜單轉化為雙向二叉樹的步驟：

前后級菜單之間轉化為父節點與左子節點。

同一菜單中存在多個選擇項，即菜單是選擇型菜單，菜單中前一個選項轉化為后一個選項的父節點，后一個選項轉化為前一個選項的右子節點。

圖3即為圖1所示的多級菜單轉換為雙向二叉樹示例。菜單A、B為選擇型菜單，菜單C、D、E、F為功能型菜單。雙向二叉樹節點A1表示選擇型菜單A的第一選項，節點A2表示菜單A的第二選項，節點F表示功能型菜單F。

2.2 多級菜單顯示信息編碼

由于各菜單需要顯示的信息眾多且顯示內容各不相同，各菜單顯示信息無法全部存儲于雙向二叉樹節點中。本文將各菜單整理為顯示函數，一菜單一顯示函數，將顯示函數及顯示信息進行映射編碼，并將編碼值存儲于雙向二叉樹節點中，編碼值表示菜單的顯示信息，易于雙向二叉樹的生成和減小設備內存開銷。本文設計采用三位字符編碼—XXX表示菜單的顯示信息，如“00r”、“11L”、“03R”等。

編碼的第1位表示當前雙向二叉樹節點對應的顯示函數。其編碼過程為將菜單需要顯示的信息整理為對應的顯示函數，創建菜單顯示函數指針數組，并將顯示函數的地址存儲于顯示函數指針數組中，顯示函數指針數組下標值即為編碼第1位的值。

編碼的第2位表示選擇型菜單選擇項，其數值由選擇菜單選擇項位于顯示界面的位置確定，如圖4所示“13R”表示當前雙向二叉樹節點表示的是選擇型菜單中在第三行顯示的選項。若菜單為功能型菜單，則編碼的第2位數值為0，如圖4所示的“20L”。由于在選擇型菜單中存在多個選擇項,本文的多級菜單雙向二叉樹節點中，選擇型菜單一選擇項即對應雙向二叉樹一節點，因此需要指定當前雙向二叉樹節點所表示的選擇項，編碼的第2位即完成此功能。

編碼的第3位表示當前二叉樹節點的類型，編碼值“r”表示該節點為雙向二叉樹的根節點，編碼值“L”表示該節點為父節點的左子樹節點，編碼值“R”表示該節點為父節點的右子樹節點。通過編碼的第3位碼值在具有多個選擇項的菜單中可以快速實現下一級菜單返回上一級菜單，只需從下一級菜單中某一選項所在的節點反向查找第一個節點類型為“L”的節點，該節點的父節點即為下一級菜單的上一級菜單所在的節點。如圖所示，“15R”所表示的菜單的上一級菜單為“00r”，如要從“15R”所表示的菜單返回“00r”所表示的菜單，只需通過“15R”反向查找第一個節點類型為“L”的節點“11L”，該節點的父節點“00r”所表示的菜單即為“15R”所表示的菜單的上級菜單。圖3所示的多級菜單編碼后的雙向二叉樹如圖4所示。

圖3 多級菜單轉化為雙向二叉樹

圖4 編碼后雙向二叉樹

2.3 雙向二叉樹的生成

已知二叉樹的先序遍歷序列和中序遍歷序列，則可以采用遞歸算法構造該二叉樹[9]。雙向二叉樹具有二叉樹的特性，且多級菜單轉化為雙向二叉樹后，可以快速獲得先序遍歷序列和中序遍歷序列。因此本文首先將多級菜單轉化為雙向二叉樹并進行編碼，再計算獲得基于編碼的先序遍歷序列和中序遍歷序列并分別存儲于兩數組中，最后利用遞歸算法實現雙向二叉樹的生成。

2.3.1 雙向二叉樹生成主要數據結構

雙向二叉樹節點的主要作用是存儲菜單需要顯示信息編碼后的編碼值，查找節點的父節點、左右子樹節點。因此雙向二叉樹節點包括編碼值、左子樹節點指針、右子樹節點指針、父節點指針四部分，雙向二叉樹節點的數據結構如下。

2.3.2 雙向二叉樹先序遍歷和中序遍歷序列

圖4所示編碼后的雙向二叉樹，其先序遍歷序列和中序遍歷序列分別為：

先序遍歷序列：00r 11L 20L 13R 30L 15R 40L 03R 50L

中序遍歷序列：20L 11L 30L 13R 40L 15R 00r 50L 03R

將雙向二叉樹的先序序列和中序序列分別存儲于先序遍歷序列數組和中序遍歷序列數組中，當多級菜單系統菜單變化時，只需要重新獲取并修改先序遍歷序列數組和中序遍歷序列數組值即可。

2.3.3 遞歸生成雙向二叉樹

通過先序遍歷序列找到雙向二叉樹的根節點，生成根節點，再通過根節點從中序遍歷序列中找到二叉樹的左子樹和右子樹。

在根節點的左子樹中，通過先序遍歷序列找到左子樹的根節點，生成左子樹根節點，再通過左子樹根節點從中序遍歷序列中找到左子樹的左子樹和右子樹。

在根節點的右子樹中，通過先序遍歷序列找到右子樹的根節點，生成右子樹根節點，通過右子樹根節點從中序遍歷序列中找到右子樹的左子樹和右子樹。

依次類推，直到序列的長度小于等于零，即完成雙向二叉樹的生成。

圖5 遞歸生成雙向二叉樹

3 基于雙向二叉樹的多級菜單系統測試

系統測試平臺采用STM32單片機+OLED12864+按鍵的方式完成。按鍵采用4個獨立機械按鍵，上（UP）、下（DOWN）、確定（ENTER）、返回（BACK）。上（UP）、下（DOWN）按鍵功能是同級多選項菜單選項之間的切換，確定（ENTER）按鍵功能是上一級菜單進入下一級菜單，返回（BACK）按鍵功能是下一級菜單返回上一級菜單。

3.1 多級菜單系統功能測試

經測試基于雙向二叉樹的多級菜單系統通過上（UP）、下（DOWN）、確定（ENTER）、返回（BACK）按鍵可以進行流暢的切換。圖1所示多級菜單部分測試界面圖6所示。

圖6 多級菜單功能選擇界面

3.2 多級菜單系統功能升級測試

多級菜單系統在圖1所示多級菜單系統的基礎上增加了LED狀態監測功能。升級后的多級菜單系統雙向二叉樹結構圖如7所示。

多級菜單系統升級后的雙向二叉樹先序遍歷序列和中序遍歷序列分別為：

先序遍歷序列：00r 11L 20L 13R 30L 15R 40L 17R 60L 03R 50L

中序遍歷序列：20L 11L 30L 13R 40L 15R 60L 17R 00r 50L 03R

將新的先序遍歷序列和中序遍歷序列填寫入先序遍歷序列數組和中序遍歷序列數組中，利用遞歸算法重新生成雙向二叉樹。上（UP）、下（DOWN）、確認（ENTER）、返回（BACK）按鍵能夠流暢的切換升級后多級菜單系統。部分升級后的多級菜單系統測試圖片如圖8所示。

圖7 系統升級后的雙向二叉樹結構圖

圖8 升級后的功能選擇界面

4 結束語

本文介紹了一種基于雙向二叉樹的多級菜單設計與實現。基于雙向二叉樹的多級菜單設計邏輯清晰，實現簡單，且多級菜單系統升級時只需重新獲取多級菜單升級后轉化的雙向二叉樹的先序遍歷序列和中序遍歷序列即可完成系統升級，降低了多級菜單的升級難度和工作量。可以廣泛應用于具有多功能和多數據顯示的智能電子設備中，具有極大的工程實用價值和參考價值。