数据结构 二叉排序树 操作及实现
2023-09-11 14:14:59 时间
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; typedef struct Bitnode { int data; struct Bitnode *lchild,*rchild; } Bitnode,*Bitree; int Searchtree(Bitree T,int num,Bitree F,Bitree &P) //在二叉树T种查找元素num F表示前驱 P表示num元素所在的节点 { if(T==NULL) //未找到该元素 { P=F; //p表示num元素应当在的位置的前驱 return 0; } else if(T->data==num) { P=T; return 1; } else if(T->data<=num) Searchtree(T->rchild,num,T,P); else Searchtree(T->lchild,num,T,P); } void print_in(Bitree &T) //中序遍历排序二叉树 { if(T!=NULL) { print_in(T->lchild); printf("%d ",T->data); print_in(T->rchild); } return; } void insertTree(Bitree &T,int num) //在二叉排序树T中插入元素NUM { Bitree P,s; int flag=Searchtree(T,num,NULL,P); if(flag==0) { s=(Bitree)malloc(sizeof(Bitnode)); s->data=num; s->lchild=NULL; s->rchild=NULL; if(T==NULL) T=s; else if(num<P->data) P->lchild=s; else P->rchild=s; } return; } void deletenode(Bitree &T) //删除该节点 { Bitree q,s; if(T->rchild==NULL) { q=T; T=T->lchild; free(q); } else if(T->lchild==NULL) { q=T; T=T->rchild; free(q); } else { q=T; s=q->lchild; while(s->rchild) { q=s; s=s->rchild; } T->data=s->data; if(T==q) //T=q 表示 while循环没有运行 T的左儿子的右子树没有节点 q->lchild=s->lchild; else q->rchild=s->lchild; free(s); } return; } void Deletetree(Bitree &T,int num) //在树种删除元素num { if(T==NULL) return; if(T->data<num) Deletetree(T->rchild,num); else if(T->data>num) Deletetree(T->lchild,num); else //找到同样的节点 删除节点操作 { // cout<<111<<endl; deletenode(T); } return; } int main() { int m,n,k; int a; Bitree T=NULL; Bitree q; int i,j; printf("输入n个元素和k次查找操作和m次删除操作:\n"); scanf("%d%d%d",&n,&k,&m); while(n--) { int num; scanf("%d",&num); insertTree(T,num); } printf("中序遍历结果\n"); print_in(T); cout<<endl; while(k--) { printf("请输入要查找的元素:\n"); scanf("%d",&a); int ans=Searchtree(T,a,NULL,q); cout<<ans<<endl; } while(m--) { printf("请输入要删除的元素:\n"); scanf("%d",&a); Deletetree(T,a); print_in(T); cout<<endl; } return 0; } 測试数据: 8 3 3 5 7 8 9 10 15 3 1 9 2 5 10 1 15
相关文章
- 数据结构之---C语言实现拓扑排序AOV图
- Java数据结构与算法之排序
- Java中对数组的排序方法总汇分析
- 数据结构与算法分析(排序,递归,链表)
- linux下sort对中文排序
- JS Leetcode 154. 寻找旋转排序数组中的最小值 II 题解分析
- 【创】数据结构----排序-----插入、冒泡、快排
- 【数据结构初阶】直接插入排序和希尔排序&链表排序
- 数据结构:排序的基本概念
- 力扣解法汇总1752. 检查数组是否经排序和轮转得到
- JAVA中sort()排序解析
- Legal or Not HDU - 3342 (拓扑排序)
- 数据结构 | 【排序】外部排序
- sql语句中order by 多个字段同时排序的应用
- 数据结构 | 十大排序超硬核八万字详解【附动图演示、算法复杂度性能分析】
- 数据结构 | 排序算法——插入排序与希尔排序
- 数据结构之详解【排序算法】
- 【软考】数据结构之5大排序(一)
- 【日常学习】【搜索/排序+字符串】洛谷1012/1107 最大整数题解
- 白话经典算法系列之六 高速排序 高速搞定
- table排序
- 阮老师谈词条排序
- 数据结构——排序
- 王道数据结构 (34) 拓扑排序
- 王道数据结构 (16) 折半查找排序
- 43数据结构与算法分析之---选择排序
- 数据结构之排序 --- 插入排序