数据结构二叉排序树的实现(用顺序和二叉链表作存储结构)课程设计.doc

《数据结构二叉排序树的实现(用顺序和二叉链表作存储结构)课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、，应对数据结构进行设计。本体主要会用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。四、算法设计算法设计思想..二插链表作存储结构：建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结

3、点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。在进行算法设计时，应将题目分为五个函数模块：1、中序遍历，符合升序输出voidinorder(node*&root){if(root!=NULL){inorder(root->left);cout<data<<'';inorder(root->right);}}..2、在查找树中插入元素voidinsert(node*&ptr,intitem){if(ptr==NULL)ptr=newnode(item);elseif(itemdata

4、)insert(ptr->left,item);elseinsert(ptr->right,item);}3、在查找树中查找元素node*find(node*&ptr,intitem){if(ptr==NULL)returnNULL;if(ptr->data==item)returnptr;elseif(itemdata)find(ptr->left,item);elsefind(ptr->right,item);}..4、在查找树中查找肯定存在的元素,并返回其引用node*&findy(node*&ptr,intitem){if(ptr->

5、data==item)returnptr;elseif(itemdata)findy(ptr->left,item);elsefindy(ptr->right,item);}node*rl(){returnleft;}node*rr(){returnright;}5、删除指定值为所在结点voiddele(node*&ptr)..{if(ptr->rl()==NULL&&ptr->rr()==NULL)ptr=NULL;elseif(ptr->rr()==NULL)ptr=ptr->rl();elseptr=ptr->rr();}private

6、:intdata;node*left;node*right;};五、程序实现1、调入文件#include2、主函数intmain(){intt,i=0,j;cout<<"10计科一班杨旭（1010311114）"<>t;cout<<"输入"<>j;node*x=newnode(j);for(;i>j;x->insert(x,j);}cou

7、t<<"中序遍历为:";x->inorder(x);//作中序遍历cout<<"";cout<<"2.二叉排序树T的元素查找和删除:"<>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);}elsecout<<"无"<

8、ndl;cin>>j;}return0;}六、程序编码#include