BST的构建与查找讨论课报告.ppt

在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么。注意：本步骤强调的是做什么？而不是怎么做。 主要完成三个方面的工作： 分析并确定问题要处理的对象（数据）是什么。例如：输入数据的类型、值的范围以及输入的形式。 分析并确定要实现的功能是什么。也就是说要对输入的数据进行什么样的处理。注意：对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所涉及的数据类型，仅需对所需完成的任务做出明确的定义。 分析并确定处理后的结果如何显示。 这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；以及相应的输出结果。 * 该程序中的理想数据是整型数字。对于用户来说，你永远不知道他会输入什么数据，所以程序必须能够合理报错。 图5。6【p96】 Page ? * Page ? * BST的构建与查找 2014.12.7 * 问题描述 问题描述 利用二叉查找树（BST）实现一个动态查找表 基本要求 使用二叉树（BST）来实现。 二叉树使用链式结构（二叉链表）实现。 实现BST的构建，查找两个功能。 * 一、需求分析 * 问题分析与任务定义 分析并确定要处理的对象（数据）是什么 用户输入的节点个数和各个节点数据 分析并确定要实现的功能是什么 通过用户输入的数据，构建相对应的BST，实现节点的插 入和查找功能 分析并确定处理后的结果如何显示 在DOS界面上输出查找是否成功以及比较次数 * 输入与输出合法性 合法输入：节点个数：正整数；节点数据：小数或整数 合法输出：查找成功，比较次数为__；查找失败，比较次数为__ 非法输入：字母或者中文字符或者～！@#￥%……这一类的字符，系统应提示用户输入有误并重新输入 * 输入输出形式 输入形式： 在该程序中，用户需要输入节点个数和节点数据以及查找的节点，节点数据间使用空格隔开，当用户输入有误时提示用户输入错误并重新输入。具体格式如下： 请输入节点个数： 请依次节点数据： 请输入需查找的节点： 输出形式： 查找成功 ，比较次数为__ 查找失败，比较次数为__ 测试数据（1） 请输入节点个数：8 请依次节点数据：12,4,35,78,56,34,89,0 请输入需查找的节点：89 查找成功，比较次数为3 请输入节点个数：8 请依次节点数据：12,4,35,78,56,34,89,0 请输入需查找的节点：678 查找失败，比较次数为3 * 测试数据（2） 请输入节点个数：c 输入有误请重新输入 请输入节点个数：8 请依次节点数据：12,4,35,78,56,,89.3,A 输入有误，请重新输入 请输入节点个数：-1 结束程序 * * 二、概要设计 抽象数据类型1.在本程序中，需要对插入的节点进行检索，而BST的插入和检索的速率都是很高的，所以我们选用构建BST的方法来解决这项问题2.由用户输入的节点个数及节点数据均为正整数，可使用整型数据进行存储，并构建一个BST存储这些节点数据3.为了节约空间，使用二叉链表实现BST。先定义BST树节点ADT，再定义树的ADT * * 二叉树节点的ADT ADT Node { 数据对象 ：整型数据 数据关系 ：没有前驱的节点是根节点，有前驱无后继的节点是叶节点 基本操作： int val()；//返回结点的数值 void setLeft(Node* ) ; //设置左子结点 void setRight(Node*);//设置右子节点 Node* Left()const; //返回左子结点 Node* Right()const ;//返回右子结点 } 树的ADT（1） ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合 数据关系R: 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的 有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 * 树的ADT（2） 基本操作： void clear();//初始化操作 bool insert（const int）;//插入元素的操作 bool find(const int)const;//查找元素的操作 * 算法基本思想（1） 该算法主要包括表的构建和查询两项： 在表的构建上，通过用户输入的数据，将第一个输入的节点数据存入根节点中，从