基于双向二叉树的多级菜单设计及实现

曹阳

（重庆工商职业学院，重庆，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 结束语

本文介绍了一种基于双向二叉树的多级菜单设计与实现。基于双向二叉树的多级菜单设计逻辑清晰，实现简单，且多级菜单系统升级时只需重新获取多级菜单升级后转化的双向二叉树的先序遍历序列和中序遍历序列即可完成系统升级，降低了多级菜单的升级难度和工作量。可以广泛应用于具有多功能和多数据显示的智能电子设备中，具有极大的工程实用价值和参考价值。