查找实习报告.doc

实习报告 一．实习题： 从键盘上输 入一串正整数， 最后输入－1作为输入结束的标志。如输入的序列为：2，5，7，23，48，96，……，-1。请以这些正整数的值作为二叉排序树中的结点的数据场之值，建立一棵二叉排序树。注意：请采用动态存储方法保存这棵二叉排序树，事先并未知道该二叉排序树中的结点的个数。 需求分析： 该题目要求根据用户的输入建立一棵二叉排序树，由此可以想到需要重载输入流运算符来接收用户的输入，至于建立一棵二叉排序树是比较容易的。 设计： 通过重载输入流运算符接收用户输入的数据并不断进行插入，直到用户输入-1。 存储结构： 二叉排序树节点类： class BSTreeNode { friend class BSTree; friend class BSTreeItr; public: BSTreeNode(int n=0,BSTreeNode* l = NULL,BSTreeNode* r = NULL) :left(l),right(r),data(n){}//构造 ~BSTreeNode(){}//析构 int GetData(){return data;}//得到结点的数据值 void SetData(const int n){ data = n; } BSTreeNode* GetLeft(){return left;}//得到指向左儿子的指针 BSTreeNode* GetRight(){return right;}//得到指向右儿子的指针 void SetLeft(BSTreeNode* l){ left = l; }//设置左子树 void SetRight(BSTreeNode* r){ right = r; }//设置右子树 private: BSTreeNode* left ;//左子树指针 BSTreeNode* right;//右子树指针 int data;//数据场 } 二叉排序树类： class BSTree { friend class BSTreeItr; private: BSTreeNode* root;//根结点 BSTreeNode* current;//当前节点，为了完成遍历 public: BSTree(BSTreeNode* p = NULL) :root(p),current(root){}//构造函数 ~BSTree(){ DelTree(root); }//析构函数 void DelTree(BSTreeNode* root)//删除以root为根结点的二叉树 friend istream operator(istream input, BSTree t)//重载的输入流运算符 } 调用关系： Main -------- operator ()(二叉排序树类的成员函数) Main --------- Inorder() (二叉排序树迭代器类的成员函数) 算法实现框架： 用户手册： 用户根据程序的提示输入数据，必须是整数类型，然后程序会产生一棵二叉排序树并按中序遍历打印结果 调试报告： 1.程序调试过程中，刚开始再插入时没有考虑到根节点为空的情况，直接比较用户输入的数据和当前指针所指结点的数据场，而且数据场也没有赋初值（因为刚开始是用模板的，后来发现比较时必须用整数，改的时候忘记赋初值了），结果出现程序中断；还有就是二叉树的析构函数中用到了递归，结果忘记加递归条件了，导致后面的中序打印的语句都不执行了，最后才发现是递归条件漏掉了，改正后程序运行正常。 时间复杂度分析： （1）插入操作是查找的基础上进行的，所以时间复杂度和查找一样，是O（lgn）的 （2）遍历操作时间复杂度是O（n）的。 算法改进： 在二叉树的析构中用到了递归，递归是很慢的，对程序运行时间影响比较大，所以能改为非递归程序会比较好。 源程序附录： BSTree.h #ifndef _BSTREE_H #define _BSTREE_H #include BSTreeNode.h #includeiostream.h class BSTree { friend class BSTreeItr;