二叉树技术文档.doc

软件介绍1需求分析1.1需求概述 树型结构是一类重要的非线性数据结构，其中树和二叉树的应用最为广泛。此软件旨在帮助同学们学习二叉树的创建、插入、删除、遍历、线索化、查找等相关知识和操作，配有形象的图形演示，可以直观地展示二叉树的相关操作，给同学留下深刻的印象，达到事半功倍的效果。1.2 术语定义l 树与二叉树是两种同的数据结构，不要误认为两者上下级的关系。l 二叉树的特点是每个结点至多只有两棵子树，二叉树的子树有左右之分，次序不能颠倒。二叉树的创建是指将用户输入的一串字符串按照用户的要求创建成一棵二叉树，这棵二叉树不一定是满树。此二叉树中不能包含相同的字符。否则向用户报错。l 二叉树的遍历是指按照某种搜索路径巡防树中的所有节点，使得每个结点被访问一次，且仅被访问一次。其中包括3种搜索路径：前序、中序、后序。前序是指先访问根节点，而后依次访问左、右子树。中序是指先中序遍历左子树，然后访问根节点，之后中序遍历右子树。后序是指首先依次遍历左、右子树，最后访问根节点。任何一种遍历方法都要用到递归的算法。l 二叉树的线索化：首先要了解线索的含义，线索是指每个结点中都包含指向该节点的前驱和后继的指针。加上线索的二叉树成为线索二叉树。对二叉树以某种遍历使其变为线索二叉树的过程即为线索化。依据遍历的方法不同，线索化的过程也可分为3种：前序、中序和后序。此时是以一定的规则将二叉树中的节点排列成一定的线性序列，这实际上是一个对非线性结构线性化的过程，使每一个节点在这些线性序列中有且只有一个直接前驱和一个直接后继。l 叶子是指二叉树的某个结点同时没有左、右孩子。查找叶子节点即是通过某种遍历方法找到叶子节点。l 节点查询是指：首先由用户输入想要查找的节点的内容，比如查找a。然后通过某种遍历方法找到a节点。若不存在此节点，则报错，要求用户重新输入。l 二叉树的插入是一个比较繁琐的过程。该软件可实现向任意位置插入原树中不存在的节点。l 二叉树的删除是指将用户想要删除的节点、该节点的左右子树都删除。1.3 功能需求1.3.1 系统前台 用户可通过界面的提示选择将要演示的内容，在当前界面即可演示相应的动态效果。1.3.2 系统后台 系统可根据接收到的用户输入的命令符，进行创建、遍历、线索化、插入、删除子树、查找任意节点、求树高等的动态演示。2 软件设计2.1 整体流程图显示相关的提示创建树插入删除查找（叶子）遍历线索化返回创建树是否2.2界面设计尽量使界面合理美观。当刚进入软件时，界面中央会显示以下字样“welcome to study binary tree”。而后会显示本系统命令的提示。演示开始后，屏幕的上半部分区为图形演示区，下半部分为文本提示区。2.3操作设计首先由用户输入命令字符。只有当显示出“Press any key to exit“的字样时，整个操作才是完整结束。3 问题及解决方案总结l 递归的运用。在二叉树的创建、遍历、线索化、查找、删除、插入等多个功能模块都要用到递归算法。递归是一种逻辑性很强的算法。运用递归的程序，可以使程序更简洁。l 通过自学相关的文件知识，可以实现按照用户的需求创建树。l 线索化实现的时候遇到了很大的困难。前序、中序和后序都是通过递归实现的，但是它们在某些方面又小有差异。l 二叉树的删除、插入设计的时候,因为涉及到图形的变化，所以是比较困难的一部分。尝试不同的思路，大胆运用递归，可以起到事半功倍的效果。l 理清思路，各个功能模块逐个实现。4 软件使用说明4.1系统整体流程说明使用次软件时，首先会在屏幕的中央显示“welcome to study binary tree”。 用户需要根据相关的提示来进行下一步的操作。在屏幕的底部显示“input the command you want to do:“的字样,若输入错误，则会显示”Press any key to continue“字样。 用户按下任意键即可进行后续操作，用户可以在任意时刻查询帮助提示。4.2业务功能说明l 使用次软件时，首先会在屏幕的中央显示“welcome to study binary tree!“的字样，如下图：l 用户按下任意键即可进行后续操作;l 此时屏幕上显示帮助，提示用户若想实现某种功能应输入哪些命令字符;l 创建树，如下图：l 求树高,如