数据结构课程设计报告二叉排序树的实现

一、设计题目1、题目：二叉排序树的实现 (用顺序和二叉链表作存储结构 )2、要求（功能）：1) 以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；二、需求分析建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。

该题目包括三方面的容：一个是二叉排序树的建立，而是二叉树的中序遍历，三是二叉树元素的查找并删除。

三、数据结构设计在写算法之前，应对数据结构进行设计。

本体主要会用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。

四、算法设计算法设计思想二插链表作存储结构：建立二插排序树采用边查找边插入的方式。

查找函数采用递归的方式进行查找。

如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。

然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。

在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。

如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。

在进行算法设计时，应将题目分为五个函数模块：1、中序遍历，符合升序输出void inorder(node *&root){if(root!=NULL){inorder(root->left);cout<<root->data<<' ';inorder(root->right);}}2、在查找树中插入元素void insert(node *&ptr,int item) {if(ptr==NULL)ptr=new node(item);else if(item<ptr->data)insert(ptr->left,item);else insert(ptr->right,item);}3、在查找树中查找元素node *find(node *&ptr,int item) {if(ptr==NULL)return NULL;if(ptr->data==item)return ptr;else if(item<ptr->data)find(ptr->left,item);else find(ptr->right,item); }4、在查找树中查找肯定存在的元素,并返回其引用node *&findy(node *&ptr,int item){if(ptr->data==item)return ptr;else if(item<ptr->data)findy(ptr->left,item);else findy(ptr->right,item);}node* rl(){return left;}node* rr(){return right;}5、删除指定值为所在结点void dele(node *&ptr)if(ptr->rl()==NULL&&ptr->rr()==NULL)ptr=NULL;else if(ptr->rr()==NULL)ptr=ptr->rl();elseptr=ptr->rr();}private:int data;node *left;node *right;};五、程序实现1、调入文件#include <iostream>2、主函数int main(){int t,i=0,j;cout<<" 10计科一班旭（1010311114）"<<endl;cout<<"1.二叉排序树T的输入:"<<endl;cout<<"输入数字个数(结点个数):";cin>>t;cout<<"输入"<<t<<"个数字，数字之间用空格隔开:"; cin>>j;node *x=new node(j);for(;i<t-1;i++){cin>>j;x->insert(x,j);}cout<<"中序遍历为:";x->inorder(x); //作中序遍历cout<<"\n";cout<<"2.二叉排序树T的元素查找和删除:"<<endl; cout<<"\n输入操作(当输入-1时程序结束):"<<endl; cin>>j;while(j!=-1){node *t=x->find(x,j); //定位结点if(t!=NULL){node *&y=x->findy(x,j);x->dele(y);cout<<"中序遍历为:";x->inorder(x);}else cout<<"无"<<j;cout<<"\n输入操作(当输入-1时程序结束):"<<endl;cin>>j;}return 0;}六、程序编码#include <iostream>using namespace std;class node{public:node(int i):data(i),left(NULL),right(NULL){}void inorder(node *&root) //中序遍历，符合升序输出{if(root!=NULL){inorder(root->left);cout<<root->data<<' ';inorder(root->right);}}void insert(node *&ptr,int item) //在查找树中插入元素{if(ptr==NULL)ptr=new node(item);else if(item<ptr->data)insert(ptr->left,item);else insert(ptr->right,item);}node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。

数据结构实验报告班级：信息与计算科学专业1102班学号： 1108060214姓名：朱晓东设计日期：2013.6.6西安科技大学计算机学院1.实验报告编写一个演示运用二叉排序树进行数据的的排序、插入、删除、查找等操作的程序。

2.需求分析本演示程序用vc6.0编写，完成数据的排序功能，同时能够进行数据的创建、插入、删除、查找。

（1）输入的形式和输入值的范围：创建二叉排序树时输入较多的值；插入元素时需要输入插入的元素的值；删除元素时输入元素的值；查找操作时需要输入元素的值。

所有输入中，元素的值都是整数。

（2）输出的形式：在创建、插入、删除的操作后，均显示操作后的元素的排序状况，有小到大排序。

（3）程序所能达到的功能：完成二叉排序树的生成、插入、删除、查找操作。

（4）测试数据：①插入操作中依次输入10 9 11 8 12 0（本程序是以0元素为为结束标志）；②查找操作中输入13；③插入操作中输入13；3概要设计本程序包含8个函数：（1）主函数main()（2）创建二叉排序树函数BSTCreate(BiTree* bt)（3）显示操作菜单函数menu()（4）显示二叉排序树的内容函数BSTShow(BiTree bt)（5）插入元素函数BSTInsert(BiTree* bt,DataType key)（6）删除元素函数BSTDelete(BiTree* bt,DataType key)（7）查找元素函数BSTSearch(BiTree bt,DataType key)（8）查找要删除的元素的函数DeleteNode(BiTree* bt)各函数之间的关系如下：BSTCreate(BiTree* bt)menu()BSTShow(BiTree bt)mainBSTInsert(BiTree* bt,DataType key)BSTDelete(BiTree* bt,DataType key) DeleteNode(BiTree* bt)BSTSearch(BiTree bt,DataType key)4.详细设计实现概要设计中定义的所有数据类型，对每个操作给出伪码算法。

二叉排序实现课程设计一、课程目标知识目标：1. 理解二叉排序树的基本概念，掌握其结构特点及操作原理；2. 学会使用二叉排序树进行数据排序，并掌握二叉排序树的插入、删除、查找等基本操作；3. 了解二叉排序树与其他排序算法的优缺点，明确其适用场景。

技能目标：1. 能够独立构建二叉排序树，进行数据的排序与查找；2. 能够分析并解决二叉排序树在实际应用中遇到的问题，如平衡二叉树、优化查找效率等；3. 能够运用所学知识，解决实际生活中的排序问题。

情感态度价值观目标：1. 培养学生的逻辑思维能力和问题解决能力，使其在面对复杂问题时，能够运用所学知识进行分析和解决；2. 增强学生的团队协作意识，通过小组讨论和实践，培养学生的沟通能力和合作精神；3. 激发学生的学习兴趣，使其在掌握二叉排序树的基础上，探索更多数据结构与算法的知识，为以后的学习打下坚实基础。

课程性质：本课程为数据结构与算法领域的基础课程，旨在帮助学生掌握二叉排序树的基本概念与操作方法，提高其编程实践能力。

学生特点：学生具备一定的编程基础，熟悉基本的数据结构和算法，但对二叉排序树的理解和应用尚浅。

教学要求：结合学生特点，注重理论与实践相结合，通过案例分析和动手实践，使学生深入理解二叉排序树，提高其编程水平。

同时，注重培养学生的逻辑思维和团队协作能力，提高其综合素质。

二、教学内容1. 引言：介绍排序算法在计算机科学中的应用，引出二叉排序树的概念及其重要性。

- 排序算法概述- 二叉排序树的基本概念2. 二叉排序树的构建与性质：- 二叉排序树的定义及结构- 二叉排序树的构建方法- 二叉排序树的性质与判定3. 二叉排序树的基本操作：- 插入操作- 删除操作- 查找操作- 遍历操作4. 二叉排序树的优化与应用：- 平衡二叉树的概念及实现- 二叉排序树在实际应用中的优化- 二叉排序树与其他排序算法的性能比较5. 实践与案例分析：- 动手实践：构建二叉排序树，实现基本操作- 案例分析：解决实际问题，分析二叉排序树的优缺点教学内容安排与进度：1. 引言与二叉排序树的构建：1课时2. 二叉排序树的基本操作：2课时3. 二叉排序树的优化与应用：2课时4. 实践与案例分析：3课时教材章节关联：1. 《数据结构与算法》第三章：树与二叉树2. 《数据结构与算法》第四章：二叉树的应用教学内容旨在帮助学生系统地掌握二叉排序树的相关知识，结合实践与案例分析，提高学生的编程实践能力和问题解决能力。

中北大学数据结构课程设计说明书2011年12月20日1.设计任务概述：功能描述：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

2.本设计所采用的数据结构二叉树及二叉链表3.功能模块详细设计3.1 详细设计思想建立二叉排序树采用边查找边插入的方式。

查找函数采用递归的方式进行查找。

如果查找到相等的则插入其左子树。

然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。

在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。

如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。

3.2 核心代码（1）主菜单模块int main(){LNode root=NULL;int Num,a,x;printf("\n\n *******************************\n");printf(" ************主菜单*************\n");printf(" *1:进行中序排列 *\n");printf(" *2:进行删除操作 *\n");printf(" *3:退出 *\n");printf(" *******************************\n");printf("请输入要进行操作的数字以0结束：\n");运行结果（3）中序遍历模块void view(LNode p){//中序遍历函数if(p){view(p->lch);printf("%d ",p->date);view(p->rch);//递归调用return;}return;}运行结果（3）删除模块LNode DelNode(LNode t,int x) {LNode p=t;LNode q=NULL;LNode s;LNode f;while(p!=NULL){if(p->date==x){break;}q=p;if(x<=p->date){p=p->lch;}else{p=p->rch;}}if(p==NULL){printf("不存在您要删除的数 %d !",x);return p;}if(p->lch){s=p->lch; //s指向其左子树;f=p->lch; //f指向其左子树;while(s-> rch)//搜索左子树的最右边的叶子结点{f=s;s=s->rch;}p->date=s->date;if(f !=s){ //若不是p的左孩子，把r的左孩子作为r的父亲的右孩子f-> rch=s->lch;}else {p->lch = s->lch; //否则结点p的左子树指向s的左子树}free(s);return p;}else{if(q->lch==p){q->lch = p->rch;}else{q->rch = p->rch;}free(p);return q;}}3.3 程序运行结果4.课程设计心得、存在问题及解决方法通过这次课程设计，我进一步的懂得了二叉链表的建立方法，进一步的了解了二叉排序树的构造方法。

题目二叉排序树的实现一、开发背景数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。

本课程设计中的二叉排序树，一共要实现四项基本的功能。

它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。

C语言是一种结构化语言。

它层次清晰，便于按模块化方式组织程序，易于调试和维护。

Ｃ语言的表现能力和处理能力极强。

它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。

它还可以直接访问内存的物理地址，进行位(bit)一级的操作。

由于Ｃ语言实现了对硬件的编程操作，因此Ｃ语言集高级语言和低级语言的功能于一体。

既可用于系统软件的开发，也适合于应用软件的开发。

C是C++的基础，C++语言和Ｃ语言在很多方面是兼容的，C++程序员可以利用C++与C的兼容性而直接并有效的使用大量现成的程序库，从而开发出更简洁更高效的系统。

需求分析：建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。

该题目包括三方面的内容：一个是二叉排序树的建立，而是二叉树的中序遍历，三是二叉树元素的查找并删除。

了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

关键词：二叉排序树；中序遍历；搜索结点；删除结点；C\C++二、课程设计题目1、二叉排序树的实现问题描述：用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

课程设计报告——数据结构题目：二叉排序树姓名：学号：专业：班级：指导老师：年月日目录一、课程设计简介 (3)二、原理分析及流程 (3)2.1、原理分析............................................................. (3)2.2、流程图........................................................................ .. (4)1、main()函数 (4)2、创建........................................................................ . (4)3、插入........................................................................ . (5)4、查找........................................................................ . (6)5、中序遍历输出 (7)三、算法描述 (8)3.1、存储结构 (8)3.2、插入算法 (8)3.3、查找算法 (9)3.4、删除算法 (10)四、小结与体会 (12)五、程序执行过程 (13)5.1、创建二叉排序树并中序输出.........................................13 5.2、插入并中序输出.. (13)5.3、查找........................................................................ . (14)六、程序清单 (14)一、课程设计简介1.1、题目：二叉排序树相关操作1、创建二叉排序树；2、插入给定值；3、查找给定值；4、删除给定值的结点。

实验报告课程名称数据结构课程设计题目名称二叉树的实现学生学院应用数学学院专业班级 14信安1班学号 **********学生姓名阮志敏指导教师刘志煌2016年12月 9 日二叉排序树的实现一、内容和要求。

1)编程实现二叉排序树，包括生成、插入、删除；2)对二叉排序树进行先根、中根和后根非递归遍历；3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。

4)分别用二叉排序树和数组去存储一个班（50人以上）的成员信息（至少包括学号、姓名、成绩3项），对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？5)格式按照作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。

二、解决方案和关键代码1.二叉排序树的实现。

1)首先定义二叉树的结构体，代码如下：struct TreeNode;typedef struct TreeNode *TreePosition;typedef struct TreeNode *SearchTree;typedef struct TreeNode *Tree;typedef int TreeElementType;struct TreeNode {//二叉树TreeElementType element;//节点中的元素SearchTree left;//左儿子SearchTree right;//右儿子int leght;//节点的深度，用于打印int position;//节点的位置，用于打印};2)实现插入和生成二叉树节点的方法。

在这里用到了递归插入的方法。

SearchTree insertTreeNode(TreeElementType x,SearchTree tree){if(tree == NULL) {tree = makeTree(x,NULL,NULL);//插入在该处}else if(x < tree->element) {tree->left = insertTreeNode(x,tree->left);}else if(x > tree->element) {tree->right = insertTreeNode(x,tree->right);}//如果相等，什么也不做return tree;}当tree == NULL时，就是递归终止的条件，也是插入该节点的地方，在这里，用makeTree()方法创建一个节点，其代码如下：static SearchTree makeTree(TreeElementType x,SearchTree left,SearchTree right) {SearchTree node = (SearchTree)malloc(sizeof(struct TreeNode));if(node == NULL){printf("make TreeNode fail!\n");}else {node->element = x;node->left = left;node->right = right;}return node;}3)实现二叉树节点删除的方法。

＃＃大学数据结构课程设计报告题目：二叉排序树的实现院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 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) 查找二叉排序树T3.输入输出输入: 输入数列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);cout<<root->data<<' ';inorder(root->right);}}void insert(node *&ptr,int item) //在查找树中插入元素{if(ptr==NULL)ptr=new node(item);else if(item<ptr->data)insert(ptr->left,item);else insert(ptr->right,item);}node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。

数据结构课程设计一、引言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。

该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。

通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。

数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。

学习数据结构的最终目的是为了获得求解问题的能力。

对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。

实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。

相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。

二、课程设计目的本课程是数据结构课程的实践环节。

主要目的在于加强学生在课程中学习的相关算法和这些方法的具体应用，使学生进一步掌握在C++或其他语言中应用这些算法的能力。

通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。

三、内容设计要求二叉排序树的实现：用顺序和二叉链表作存储结构1）以回车（‘\n’）为输入结束标志，输入数列L,生成一棵二叉排序树T;2)对二叉排序树T作中序遍历，输出结果；3）输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历（执行操作2）；否则输出信息“无x”。

（一）问题分析和任务定义对问题的描述应避开具体的算法和涉及的数据结构，它是对要完成的任务作出明确的回答，强调的是做什么，而不是怎么做。

（二）详细的设计和编码算法的具体描述和代码的书写。

（三）上机调试源程序的输入和代码的调试。

课程设计报告——数据结构题目：二叉排序树姓名：学号：专业：班级：指导老师：年月日目录一、课程设计简介 (3)二、原理分析及流程 (3)2.1、原理分析 (3)2.2、流程图 (4)1、main()函数 (4)2、创建 (4)3、插入 (5)4、查找 (6)5、中序遍历输出 (7)三、算法描述 (8)3.1、存储结构 (8)3.2、插入算法 (8)3.3、查找算法 (9)3.4、删除算法 (10)四、小结与体会 (12)五、程序执行过程 (13)5.1、创建二叉排序树并中序输出 (13)5.2、插入并中序输出 (13)5.3、查找 (14)六、程序清单 (14)一、课程设计简介1.1、题目：二叉排序树相关操作1、创建二叉排序树；2、插入给定值；3、查找给定值；4、删除给定值的结点。

1.2、报告要求：1、封面;2、题目与流程图或模块图;3、程序清单和运行结果;4、小结(收获和体会);5、装订成册。

1.3、目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。

提高学生适应实际，实践编程的能力。

二、原理分析及流程2.1、原理分析：根据题目要求，要实现这些功能，就必须创建一个菜单。

这个菜单设置在main（）函数里面，然后使用while()...switch()语句进行循环调用相关函数，以达到实现相关功能的目的。

2.2、流程图：1、main（）函数：23、插入：4、查找：5、中序遍历输出：三、算法描述3.1、存储结构定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：#include <stdio.h>#define null 0typedef int keytype;typedef struct node{keytype key;struct node *lchild,*rchild;}bstnode,*bstree;3.2、插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。

中北大学数据结构课程设计说明书2011年12月20日1.设计任务概述：功能描述：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

2.本设计所采用的数据结构二叉树及二叉链表3.功能模块详细设计详细设计思想建立二叉排序树采用边查找边插入的方式。

查找函数采用递归的方式进行查找。

如果查找到相等的则插入其左子树。

然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。

在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。

如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。

核心代码（1）主菜单模块int main(){LNode root=NULL;int Num,a,x;printf("\n\n*******************************\n");printf(" ************主菜单*************\n");printf(" *1:进行中序排列*\n");printf(" *2:进行删除操作*\n");printf(" *3:退出*\n");printf("*******************************\n");printf("请输入要进行操作的数字以0结束：\n");运行结果（3）中序遍历模块void view(LNode p){程设计心得、存在问题及解决方法通过这次课程设计，我进一步的懂得了二叉链表的建立方法，进一步的了解了二叉排序树的构造方法。

《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

2) 输出树的深度，最大元，最小元。

二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。

递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。

直到递归全部结束。

下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。

具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。

再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。

具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。

如此循环直至结点指针和栈均为空，遍历结束。

最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。

课程设计课程名称数据构造课程设计题目名称二叉排序树的实现学院应用数学学院专业班级学号学生XX指导教师2013 年12 月26 日1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进展先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。

4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、XX、成绩3项),比照查找效率，并说明为什么二叉排序树效率高〔或者低〕。

2. 函数模块：2.1.主函数main模块功能1.通过bstree CreatTree()操作建立二叉排序树。

2.在二叉排序树t中通过操作bstree InsertBST(bstree t,intkey,nametype name,double grade)插入一个节点。

3. 从二叉排序树t中通过操作void Delete(bstree &p)删除任意节点。

4. 在二叉排序树t中通过操作bstnode *SearchBST(bstree t,keytype key)查找节点。

5. 在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息6. 非递归遍历二叉排序树。

7. 定义函数void pare()对数组和二叉排序树的查找效率进展比拟比拟。

2.2创立二叉排序树CreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进展插入。

最后，返回根节点T。

2.3删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。

假设二叉排序树上删除节点为*p〔指向节点的指针为p〕，其双亲节点为*f〔节点指针为f〕。

假设*p节点为叶子节点，那么即左右均为空树，由于删去叶子节点不破坏整棵树的构造，那么只需修改其双亲节点的指针即可；假设*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；假设*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱〔或直接后继〕替代*p，然后再从二叉排序树中删去它的直接前驱〔或直接后继〕。

课程设计课程名称数据结构课程设计题目名称二叉排序树的实现学院应用数学学院专业班级学号学生姓名指导教师2013 年 12 月 26 日1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。

4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明为什么二叉排序树效率高（或者低）。

2. 函数模块：.主函数main模块功能1.通过bstree CreatTree()操作建立二叉排序树。

2.在二叉排序树t中通过操作bstree InsertBST(bstree t,intkey,nametype name,double grade)插入一个节点。

3. 从二叉排序树t中通过操作void Delete(bstree &p)删除任意节点。

4. 在二叉排序树t中通过操作bstnode *SearchBST(bstree t,keytype key)查找节点。

5. 在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息6. 非递归遍历二叉排序树。

7. 定义函数void compare()对数组和二叉排序树的查找效率进行比较比较。

创建二叉排序树CreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。

最后，返回根节点T。

删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。

假设二叉排序树上删除节点为*p（指向节点的指针为p），其双亲节点为*f（节点指针为f）。

若*p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；若*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。

课程设计报告关于二叉排序树的实现一：需求分析1：基本要求a)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；b)对二叉排序树T作中序遍历，输出结果；c)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2：设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。

3:设计所采用的数据结构1:利用数组思想,通过改变数组指针来表示数组的左右子树,左子树的下标为2*i,右子树的下标为2*i+1.2：树的存储结构如下：#define N 100 /*二叉树结点的最大数目*/typedef struct{int *data; /*数组首址指针*/int lenth; /*数组长度*/}BST;4：每个模块的功能要求:初始化一个数组，开辟一块内存空间，先建立一个插入函数。

创建一棵二叉树，中序遍历该树在二叉排序树中查找其关键字等于给定值的结点是否存在删除所给结点，并对新树中序遍历最后，可以判断所给树是否为平衡树二：概要设计1:使用树的动态顺序存储结构，先初始化一个数组。

2：建立一个插入函数，通过调用该函数边查找边插入建立二叉排序树3：通过递归调用，中序遍历树，以及判断其是否为平衡树4：q.data=(int *)malloc(N*sizeof(int)); /*重新初始化一个数组Q*/ 新的数组储存删除给定结点的新树5：要实现二叉排序树，要先创建二叉排序树，在以下程序中利用边查找边插入来建立二叉排序树。

BST create(int *crew,int num) /*创建二叉排序树的函数*/{BST T;int i,j;T.data=(int *)malloc(N*sizeof(int)); /*数组初始化*/for(j=0;j<N;j++) T.data[j]=0;T.lenth=0;for(i=0;i<num;i++) /*边查找边插入建立二插排序树*/{insert(T,1,crew[i]);++T.lenth; /*记录树中结点的个数*/}return (T);}在这个过程中，调用了已经建立的函数insert(T,1,crew[i]); 为新结点查找到相应的位置，将其插入树中。