基于雙向二叉樹的多級(jí)菜單設(shè)計(jì)及實(shí)現(xiàn)

曹陽

（重慶工商職業(yè)學(xué)院，重慶，401520）

0 引言

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

目前多級(jí)菜單系統(tǒng)多采用索引號(hào)串聯(lián)菜單的方式實(shí)現(xiàn)[1～3]。使用索引號(hào)串聯(lián)菜單在多級(jí)菜單設(shè)計(jì)及實(shí)現(xiàn)過程中涉及較多的數(shù)據(jù)結(jié)構(gòu)和關(guān)鍵參數(shù)，當(dāng)多級(jí)菜單系統(tǒng)升級(jí)或修改時(shí)，需要修改較多的數(shù)據(jù)結(jié)構(gòu)和關(guān)鍵參數(shù)，增加軟件升級(jí)難度和工作量?；诖?，本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于雙向二叉樹的多級(jí)菜單系統(tǒng)，當(dāng)多級(jí)菜單系統(tǒng)升級(jí)或變化時(shí)，只需重新獲取雙向二叉樹先序遍歷序列和中序遍歷序列即可完成多級(jí)菜單系統(tǒng)的升級(jí)，降低了系統(tǒng)升級(jí)難度和工作量。

1 基于雙向二叉樹的多級(jí)菜單模型

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

圖1 多級(jí)菜單

多級(jí)菜單系統(tǒng)在結(jié)構(gòu)上和數(shù)據(jù)結(jié)構(gòu)中的非線性結(jié)構(gòu)—樹型結(jié)構(gòu)相似，是一種典型的多層次嵌套結(jié)構(gòu)，多級(jí)菜單系統(tǒng)可以采用樹型結(jié)構(gòu)表示。多級(jí)菜單可以直觀的轉(zhuǎn)化為樹型結(jié)構(gòu)中的多叉樹，但是由于多叉樹中父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量是不確定的，存儲(chǔ)上難以采用統(tǒng)一的存儲(chǔ)結(jié)構(gòu)表示，實(shí)現(xiàn)困難。二叉樹是一種常用的樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)節(jié)點(diǎn)上至多有兩個(gè)子節(jié)點(diǎn)，且節(jié)點(diǎn)的左右順序不可以任意顛倒[11]。由于二叉樹節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量是固定的，可以采用統(tǒng)一的存儲(chǔ)結(jié)構(gòu)表示，且多叉樹可以轉(zhuǎn)換為相應(yīng)的二叉樹，因此多級(jí)菜單系統(tǒng)可以采用二叉樹的結(jié)構(gòu)表示和實(shí)現(xiàn)。

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

一般的二叉樹在設(shè)計(jì)上僅支持單向訪問，即父節(jié)點(diǎn)可以訪問子節(jié)點(diǎn)，子節(jié)點(diǎn)不可以訪問父節(jié)點(diǎn)。在多級(jí)菜單系統(tǒng)中，經(jīng)常需要訪問后級(jí)菜單和返回前級(jí)菜單，以及同級(jí)菜單選項(xiàng)之間相互切換，普通的二叉樹無法實(shí)現(xiàn)多級(jí)菜單之間的相互訪問和切換。因此本文采用雙向二叉樹的方式實(shí)現(xiàn)多級(jí)菜單，父節(jié)點(diǎn)存儲(chǔ)前級(jí)菜單選項(xiàng)1的相關(guān)信息，左子節(jié)點(diǎn)存儲(chǔ)后級(jí)菜單信息，右子節(jié)點(diǎn)存儲(chǔ)前級(jí)菜單選項(xiàng)2信息，父節(jié)點(diǎn)與子節(jié)點(diǎn)之間可以相互訪問，以實(shí)現(xiàn)前級(jí)菜單，后級(jí)菜單及同級(jí)菜單多個(gè)選項(xiàng)之間的訪問和切換。雙向二叉樹結(jié)構(gòu)如圖2所示。

圖2 雙向二叉樹

2 基于雙向二叉樹的多級(jí)菜單實(shí)現(xiàn)

基于雙向二叉樹的多級(jí)菜單通過二叉樹節(jié)點(diǎn)實(shí)現(xiàn)多級(jí)菜單之間的相互切換和訪問，雙向二叉樹的構(gòu)造是實(shí)現(xiàn)節(jié)點(diǎn)之間訪問和切換的關(guān)鍵和基礎(chǔ)。雙向二叉樹構(gòu)造的設(shè)計(jì)思路是首先將多級(jí)菜單轉(zhuǎn)換為雙向二叉樹；然后將各菜單需要顯示的信息進(jìn)行映射和編碼，并將編碼值存儲(chǔ)于雙向二叉樹節(jié)點(diǎn)中，以編碼值表示各菜單顯示信息；最后根據(jù)多級(jí)菜單轉(zhuǎn)換的雙向二叉樹獲得雙向二叉樹的先序遍歷序列和中序遍歷序列，通過先序遍歷序列和中序遍歷序列利用遞歸構(gòu)造算法構(gòu)造雙向二叉樹。

2.1 多級(jí)菜單轉(zhuǎn)化雙向二叉樹

多級(jí)菜單轉(zhuǎn)化為雙向二叉樹的步驟：

前后級(jí)菜單之間轉(zhuǎn)化為父節(jié)點(diǎn)與左子節(jié)點(diǎn)。

同一菜單中存在多個(gè)選擇項(xiàng)，即菜單是選擇型菜單，菜單中前一個(gè)選項(xiàng)轉(zhuǎn)化為后一個(gè)選項(xiàng)的父節(jié)點(diǎn)，后一個(gè)選項(xiàng)轉(zhuǎn)化為前一個(gè)選項(xiàng)的右子節(jié)點(diǎn)。

圖3即為圖1所示的多級(jí)菜單轉(zhuǎn)換為雙向二叉樹示例。菜單A、B為選擇型菜單，菜單C、D、E、F為功能型菜單。雙向二叉樹節(jié)點(diǎn)A1表示選擇型菜單A的第一選項(xiàng)，節(jié)點(diǎn)A2表示菜單A的第二選項(xiàng)，節(jié)點(diǎn)F表示功能型菜單F。

2.2 多級(jí)菜單顯示信息編碼

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

編碼的第1位表示當(dāng)前雙向二叉樹節(jié)點(diǎn)對(duì)應(yīng)的顯示函數(shù)。其編碼過程為將菜單需要顯示的信息整理為對(duì)應(yīng)的顯示函數(shù)，創(chuàng)建菜單顯示函數(shù)指針數(shù)組，并將顯示函數(shù)的地址存儲(chǔ)于顯示函數(shù)指針數(shù)組中，顯示函數(shù)指針數(shù)組下標(biāo)值即為編碼第1位的值。

編碼的第2位表示選擇型菜單選擇項(xiàng)，其數(shù)值由選擇菜單選擇項(xiàng)位于顯示界面的位置確定，如圖4所示“13R”表示當(dāng)前雙向二叉樹節(jié)點(diǎn)表示的是選擇型菜單中在第三行顯示的選項(xiàng)。若菜單為功能型菜單，則編碼的第2位數(shù)值為0，如圖4所示的“20L”。由于在選擇型菜單中存在多個(gè)選擇項(xiàng),本文的多級(jí)菜單雙向二叉樹節(jié)點(diǎn)中，選擇型菜單一選擇項(xiàng)即對(duì)應(yīng)雙向二叉樹一節(jié)點(diǎn)，因此需要指定當(dāng)前雙向二叉樹節(jié)點(diǎn)所表示的選擇項(xiàng)，編碼的第2位即完成此功能。

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

圖3 多級(jí)菜單轉(zhuǎn)化為雙向二叉樹

圖4 編碼后雙向二叉樹

2.3 雙向二叉樹的生成

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

2.3.1 雙向二叉樹生成主要數(shù)據(jù)結(jié)構(gòu)

雙向二叉樹節(jié)點(diǎn)的主要作用是存儲(chǔ)菜單需要顯示信息編碼后的編碼值，查找節(jié)點(diǎn)的父節(jié)點(diǎn)、左右子樹節(jié)點(diǎn)。因此雙向二叉樹節(jié)點(diǎn)包括編碼值、左子樹節(jié)點(diǎn)指針、右子樹節(jié)點(diǎn)指針、父節(jié)點(diǎn)指針?biāo)牟糠?，雙向二叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下。

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

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

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

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

將雙向二叉樹的先序序列和中序序列分別存儲(chǔ)于先序遍歷序列數(shù)組和中序遍歷序列數(shù)組中，當(dāng)多級(jí)菜單系統(tǒng)菜單變化時(shí)，只需要重新獲取并修改先序遍歷序列數(shù)組和中序遍歷序列數(shù)組值即可。

2.3.3 遞歸生成雙向二叉樹

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

在根節(jié)點(diǎn)的左子樹中，通過先序遍歷序列找到左子樹的根節(jié)點(diǎn)，生成左子樹根節(jié)點(diǎn)，再通過左子樹根節(jié)點(diǎn)從中序遍歷序列中找到左子樹的左子樹和右子樹。

在根節(jié)點(diǎn)的右子樹中，通過先序遍歷序列找到右子樹的根節(jié)點(diǎn)，生成右子樹根節(jié)點(diǎn)，通過右子樹根節(jié)點(diǎn)從中序遍歷序列中找到右子樹的左子樹和右子樹。

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

圖5 遞歸生成雙向二叉樹

3 基于雙向二叉樹的多級(jí)菜單系統(tǒng)測(cè)試

系統(tǒng)測(cè)試平臺(tái)采用STM32單片機(jī)+OLED12864+按鍵的方式完成。按鍵采用4個(gè)獨(dú)立機(jī)械按鍵，上（UP）、下（DOWN）、確定（ENTER）、返回（BACK）。上（UP）、下（DOWN）按鍵功能是同級(jí)多選項(xiàng)菜單選項(xiàng)之間的切換，確定（ENTER）按鍵功能是上一級(jí)菜單進(jìn)入下一級(jí)菜單，返回（BACK）按鍵功能是下一級(jí)菜單返回上一級(jí)菜單。

3.1 多級(jí)菜單系統(tǒng)功能測(cè)試

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

圖6 多級(jí)菜單功能選擇界面

3.2 多級(jí)菜單系統(tǒng)功能升級(jí)測(cè)試

多級(jí)菜單系統(tǒng)在圖1所示多級(jí)菜單系統(tǒng)的基礎(chǔ)上增加了LED狀態(tài)監(jiān)測(cè)功能。升級(jí)后的多級(jí)菜單系統(tǒng)雙向二叉樹結(jié)構(gòu)圖如7所示。

多級(jí)菜單系統(tǒng)升級(jí)后的雙向二叉樹先序遍歷序列和中序遍歷序列分別為：

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

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

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

圖7 系統(tǒng)升級(jí)后的雙向二叉樹結(jié)構(gòu)圖

圖8 升級(jí)后的功能選擇界面

4 結(jié)束語

本文介紹了一種基于雙向二叉樹的多級(jí)菜單設(shè)計(jì)與實(shí)現(xiàn)?；陔p向二叉樹的多級(jí)菜單設(shè)計(jì)邏輯清晰，實(shí)現(xiàn)簡(jiǎn)單，且多級(jí)菜單系統(tǒng)升級(jí)時(shí)只需重新獲取多級(jí)菜單升級(jí)后轉(zhuǎn)化的雙向二叉樹的先序遍歷序列和中序遍歷序列即可完成系統(tǒng)升級(jí)，降低了多級(jí)菜單的升級(jí)難度和工作量。可以廣泛應(yīng)用于具有多功能和多數(shù)據(jù)顯示的智能電子設(shè)備中，具有極大的工程實(shí)用價(jià)值和參考價(jià)值。