数据结构课程设计之二叉排序树的实现.doc

＃＃大学 数据结构课程设计报告 题目： 二叉排序树的实现 院（系）： 计算机工程学院 学生姓名: 　 班级： 　 学号: 　　　　 起迄日期: 2011.6.20-2011.7.1 指导教师: 　 2010—2011年度 第 2 学期 一、需求分析 1.问题描述： 二叉排序树的实现 用顺序和二叉链表作存储结构 1) 以回车(\n)为输入结束标志,输入数列L，生成一棵二叉排 序树T； 2) 对二叉排序树T作中序遍历，输出结果； 3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”； 2.基本功能 1) 生成一棵二叉排 2) 对二叉排序树T作中序遍历 3) 查找二叉排序树T 3.输入输出 输入: 输入数列L以回车(\n)为输入结束标志 输出: 中序遍历的二叉树 二、 概要设计 1.设计思路： 首先，要创建一棵二叉排序树；必须定义二叉排序树的结点结构数据类型，并定义insert函数，在二叉排序树中插入结点。 要中序遍历二叉排序树，必然用到递归算法。先根再左再右。 要在二叉树中查找输入的元素，若存在含x的结点,则删除该结点,并作中序遍历。 2.数据结构设计： void inorder(node *root) 中序遍历，符合升序输出 void insert(node *ptr,int item) 在查找树中插入元素 node *find(node *ptr,int item) 在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 node *findy(node *ptr,int item) 在查找树中查找肯定存在的元素,并返回其引用 void dele(node *ptr) 删除值为item所在结点 3.软件结构设计 Main模块 二叉排序树模块 三、 详细设计 1.树的结点数据类型： class node { public: node(int i):data(i),left(NULL),right(NULL){} 2．主函数和其他函数的伪码算法； void inorder(node *root) //中序遍历，符合升序输出 { if(root!=NULL) { inorder(root-left); coutroot-data ; inorder(root-right); } } void insert(node *ptr,int item) //在查找树中插入元素 { if(ptr==NULL) ptr=new node(item); else if(itemptr-data) insert(ptr-left,item); else insert(ptr-right,item); } node *find(node *ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 { if(ptr==NULL) return NULL; if(ptr-data==item) return ptr; else if(itemptr-data) find(ptr-left,item); else find(ptr-right,item); } node *findy(node *ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用 { if(ptr-data==item) return ptr; else if(itemptr-data) findy(ptr-left,item); else findy(ptr-right,item); } node* rl(){return left;} node* rr(){return right;} void dele(node *ptr) //删除值为item所在结点 { if(ptr-rl()==NULLptr-rr()==NULL) ptr=NULL; e