logo资料库

数据结构综合课设二叉排序树.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.05M 资料格式：docx 举报 版权申诉
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页，剩余部分请下载后查看
    二叉排序树 【问题描述】 从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打 印等有关操作。 【基本要求】 建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度 【选作内容】 实现二叉排序树的插入、删除操作。 【算法思想】 通过建立二叉排序数，利用指针，以及执行相关操作的功能的函数完成代码，并 且满足题目所给出的要求，如：插入，删除，打印，遍历（前序遍历，中序遍历， 后序遍历），以及查找次数。但是解决问题的途径不止一种，一些还是可以利用 递归的方法来进行。然后就是一级指针和二级指针的使用，以及形参和实参，函 数的调用的使用。 【模块划分】 1. 函数的存储结构 定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中 的结点、结点类型和指针类型如下： #include #include #include typedef struct node { int data, d; struct node *lt, *rt; }ST; int times=0; 2. 判断高度 int deep(ST *root) if(!root) return -1; else return root->d; { }
    3. 四种调节 ST *RR(ST *root) { ST *p; p = root->rt; root->rt = p->lt; p->lt = root; root->d = max(deep(root->lt), deep(root->rt)) + 1; return p; } ST *LR(ST *root) { root->lt = RR(root->lt); root = LL(root); return root; } ST *RL(ST *root) { root->rt = LL(root->rt); root = RR(root); return root; } 4. 插入与建立 插入算法 在二叉排序树中插入一个新节点，首先要查找该节点在二叉 排序树中是否已经存在。若二叉排序树中不存在关键字等于 x 的 节点，则插入。 将一个关键字值为 x 的节点 s 插入到二叉排序树中，可以用 下面的方法： （1）若二叉排序树为空，则关键字为 x 的节点 s 成为二叉排 序树的根 （2）若二叉排序树非空，则将 x 与二叉排序树根进行比较， 如果 x 的值等于根节点关键值，则停止插入；如果 x 的根节点值 小于根节点关键值，则将 x 插入左子树；如果 x 的值大于根节点 关键字的值，则将×插入右子树。在左右两个子树的插入方法相同 //进行插入与建立 ST *insert(int x, ST *root) { if(!root)//这里是建立根节点 { root = (ST *)malloc(sizeof(ST)); root->data = x; root->d = 0;
    root->lt = NULL; root->rt = NULL; } else//如果不是根节点的话，需要判断他的位置，这里是根据深度与大小进 行判断的 { if(x < root->data) { root->lt = insert(x, root->lt); if(deep(root->lt) - deep(root->rt) > 1) { if(root->lt->data > x) root = LL(root); else root = LR(root); } } else if(x > root->data) { root->rt = insert(x, root->rt); if(deep(root->rt) - deep(root->lt) > 1) { if(root->rt->data < x) root = RR(root); else root = RL(root); } } } root->d = max(deep(root->rt),deep(root->lt)) + 1; return root; } 5. 删除 在二叉排序树中删除节点，首先要确定被删除的节点是否在 二叉排序树中。 若不在，则不做任何操作；否则，假设要删除的节点为 p， 节点 p 的父节点为 r，并假设 p 是 r 的左孩子。根据被删除节点 p 有无孩子，删除部分可做以下 3 中情况讨论： （1） 若 p 为叶子节点，则可令其父节点 r 的左孩子指针域 为空，直接将其删除。 （2）若 p 节点只有右子树或左子树，则可以将 p 的左子树 或右子树直接改为其双亲节点 r 的左子树。 （3）若 p 既有左子树又有右子树；将节点 s 为 p 的中序前 驱。首先找到 p 的中序前驱节点 s，然后用节点 s 的值代替节点 p 的值，再将节点 s 删除，节点 s 的原左子树改为 s 的双亲节点 q
    的右子树。 //删除 ST *DelST(ST *t,int k) { ST *p,*f,*s,*q; p=t; f=NULL; while(p) { if(p->data==k) break; f=p; if(p->data>k) p=p->lt; else p=p->rt; } if(p==NULL) return t; if(p->lt==NULL) { if(f==NULL) t=p->rt; else if(f->lt==p) f->rt=p->rt; else f->rt=p->lt; free(p); } else { q=p; s=s->lt; while(s->rt) { q=s; s=s->rt; } if(q==p) q->lt=s->lt; else q->rt=s->lt; p->data=s->data;
    free(s); } return t; } 6. 打印 //打印出序列：前序中序后序 void print(ST *root,int x) { if(root){ { if(x==1) printf("%d print(root->lt,x); print(root->rt,x); ",root->data); }//前序 else if (x==2) { print(root->lt,x); printf("%d ",root->data); print(root->rt,x); } //中序 else if(x==3) { print(root->lt,x); print(root->rt,x); printf("%d ",root->data); }//后序 else printf("该序列为空。\n"); } } 7. 查找 （1）若二叉排序树不为空，将根结点的关键字与待查关键字 进行比较，若相等，则查找成功；若根节点关键字大于待查值， 则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在 查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节 点，则查找不成功。 （2）否则，查找失败，返回 null。 //查找操作 ST *Search(int K,ST *bst)
    { ST *q; q=bst; while(q) { times++; if(q->data==K) return q; else if (Kdata) q=q->lt; else q=q->rt; } return NULL; } 8. 主函数 int main() { ST *root; int n, x; printf("输入元素的个数为：\n"); scanf("%d",&n); root = NULL; printf("请输入一列数字:\n"); while(n--) { scanf("%d", &x); root = insert(x, root); } printf("前序输出请输入 1；中序请输入 2，后序请输入 3\n"); int p; scanf("%d",&p); print(root,p); printf("\n"); printf("请输入选择插入的数字：\n"); int data; scanf("%d",&data); root=insert (data,root); printf("该树的中序遍历是：\n"); print(root,2); printf("请输入要查找的数字：\n"); int data1;
    scanf("%d",&data1); ST *lr; lr=Search(data1,root); if (lr) {printf("已找到该数字，查找次数为%d\n",times); printf("该 树的中序遍历是：\n");print(root,2); } else printf("未找到"); int data2; printf("请输入要删除的数字：\n"); scanf("%d",&data2); root=DelST(root,data2); printf("该树的中序遍历是：\n"); print(root,2); return 0; } 【源程序】 #include #include #include typedef struct node { int data, d; struct node *lt, *rt; }ST; int times=0; //这里是设置一个函数用来比较大小，方便建立二叉排序树 int max(int a, int b) { if(a < b) return b; else return a; } //用来判断高度 int deep(ST *root) { if(!root) return -1; else return root->d; } //四种调节方式：rl,lr,rr,ll ST *LL(ST *root) {
    ST *p; p = root->lt; root->lt = p->rt; p->rt = root; root->d = max(deep(root->lt), deep(root->rt)) + 1; return p; } ST *RR(ST *root) { ST *p; p = root->rt; root->rt = p->lt; p->lt = root; root->d = max(deep(root->lt), deep(root->rt)) + 1; return p; } ST *LR(ST *root) { root->lt = RR(root->lt); root = LL(root); return root; } ST *RL(ST *root) { root->rt = LL(root->rt); root = RR(root); return root; } //进行插入与建立 ST *insert(int x, ST *root) { if(!root)//这里是建立根节点 { root = (ST *)malloc(sizeof(ST)); root->data = x; root->d = 0; root->lt = NULL; root->rt = NULL; } else//如果不是根节点的话，需要判断他的位置，这里是根据深度与大小进 行判断的 { if(x < root->data) { root->lt = insert(x, root->lt);
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料