数据结构课程设计二叉排序树.pdf

6.4.1 二叉排序树基本操作的实现 专业：**** 姓名：**** 学号：**** 日期：2011-9-17 一， 问题描述 二， 需求分析 三， 概要设计 四， 详细设计 五， 测试分析 六， 源程序清单 七， 用户使用手册 八， 心得体会 1 一、 问题描述 从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、 格式化输出操作。 二、 需求分析 1. 读入给定的数据，构造二叉排序树，实现初始化。 2. 给定数据的格式为，第一行为元素个数，遇 0 退出程序。 3. 提供菜单功能，选项包括查找、插入、删除和打印等。 三、 概要设计 1.数据结构： struct node{ int num; node *chl,*chr; }; 分别定义了指向左右子树的指针。 2. 函数介绍 void Insert(const int temp,node **root); void Delete(const int key,node **p); bool Find(const int key,node *p,node *net,int depth); void Print(const node *p); bool Menu(node **root); 函数如其名，功能也亦如其名。另外为了防止边界情况，如空树或者没 有指定元素的非法删除以及查找，所以会在函数内部直接进行判断，以及状 态返回判断等。 3. 函数形参 部分形参使用引用的方式进行传递，还有些使用的是指针的指针，这样 保传入的指针指向的内容可以被修改，并且函数返回之后可以继续指向原有 2 内容。 四、 详细设计 void Insert(const int temp,node **root) { if( *root==NULL ) { *root = new node; (*root)-chl = (*root)-chr = NULL; (*root)-num = temp; } else if( (*root)-numtemp ) Insert(temp,(*root)-chr); else Insert(temp,(*root)-chl); } // 插入函数，使用递归的方式进行插入，并动态创建对象。 void Delete(const int key,node **p) { if( *p==NULL ) { cout删除错误，不存在该元素！endl; flagdel = false; return; } node *temp=NULL; if( (*p)-num==key ) { if( (*p)-chl==NULL ) { temp = *p; *p = (*p)-chr; delete temp; } else if( (*p)-chr==NULL ) { te