二叉排序树的实现数据结构课程设计
- 格式：doc
- 大小：302.33 KB
- 文档页数：12
题 目 二叉排序树的实现
一、开发背景
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设计中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。
C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。Ｃ语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于Ｃ语言实现了对硬件的编程操作，因此Ｃ语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。C是C++的基础，C++语言和Ｃ语言在很多方面是兼容的，C++程序员可以利用C++与C的兼容性而直接并有效的使用大量现成的程序库，从而开发出更简洁更高效的系统。
需求分析：建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。该题目包括三方面的内容：一个是二叉排序树的建立，而是二叉树的中序遍历，三是二叉树元素的查找并删除。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
关键词：二叉排序树；中序遍历；搜索结点；删除结点；C\C++
二、课程设计题目
1、二叉排序树的实现
问题描述：用顺序和二叉链表作存储结构实现二叉排序树：
（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
2、课程设计要求
在处理题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述，用流程图或伪代码表示。说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。在写算法之前，应对数据结构进行设计。本题主要会
用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。
三、算法思想
1、二叉排序树的定义
二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：
（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；
（2）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
（3）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
（4） 左、右子树本身又各是一棵二叉排序树
2、二叉排序树的实现
1）建立二叉排序树
建立二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点
从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。
根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：
若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。
若非空树，比较b与根结点数据data（p）
如果b
如果b≥data(p)，将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。
2）二叉排序树的中序遍历
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；否则
中序遍历左子树（L）；
访问根结点（V）；
中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕
3）二叉排序树中元素的查找
在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。
4）二叉排序树中元素的删除
对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。
四、算法实现
1、任务描述
对二叉排序树T作中序遍历,并输出结果 二叉链表作存储结构和顺序表作存储结构
输入数列L， 以回车(‘\\n’)为输入结束标志生成二叉排序树T；
输入元素x，查找二叉排序树T
找到该节点x
存在含x的结点，则删除该结点，并作中序遍历 无结点x
二叉排序树T是否为平衡二叉树 NO!
OK!
2、功能描述：
(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历，输出结果；
(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
3、功能模块详细设计——详细设计思想
建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。否则返回当前结点的上一个结点，然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。
程序主要设计了四个功能：首先是创建二叉排序树，完成后出现任务菜单，以数字代码确定，二叉排序树的中序遍历和查找，删除步骤，最后完成，结束。
对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。
删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。
4、程序模块
#include
主函数
int main()
{
int t,i=0,j;
cout<<" 10信息安全王转红（201181250122）"<
cout<<"1.二叉排序树T的输入:"<
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<
cin>>j;
node *x=new node(j);
for(;i
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x); //作中序遍历
cout<<"\n";
cout<<"2.二叉排序树T的元素查找和删除:"<
cout<<"\n输入操作(当输入-1时程序结束):"<
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<<"无"<
cout<<"\n输入操作(当输入-1时程序结束):"<
cin>>j;
}
return 0;
}
5、程序编码
1）用顺序实现;
#include "stdafx.h"
#include
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 inorder(root->right); } } void insert(node *&ptr,int item) //在查找树中插入元素 { if(ptr==NULL) ptr=new node(item); else if(itemdata) insert(ptr->left,item); else insert(ptr->right,item);} node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 {if(ptr==NULL) return NULL; if(ptr->data==item)
