一、设计题目
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<
2、在查找树中插入元素 void insert(node *&ptr,int item) {
if(ptr==NULL) ptr=new node(item); else if(item
3、在查找树中查找元素
node *find(node *&ptr,int item) {
if(ptr==NULL) return NULL; if(ptr->data==item) return ptr; else if(item
4、在查找树中查找肯定存在的元素,并返回其引用 node *&findy(node *&ptr,int item) {
if(ptr->data==item) return ptr; else if(item
node* rr() {
return right; }
5、删除指定值为所在结点 void dele(node *&ptr)