排序二叉树、查找、二分法查找、数据结构，实验报告 #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <time.h> using namespace std; typedef int ElemType ; typedef int KeyType; const int MAX_SIZE_ST=10; bool cmp( ElemType a,ElemType b ) { return a<b; } typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { ElemType *elem; int length; } SSTable; int search_seq( SSTable ST,KeyType key ) { int i=0; //找不到时为0 ST.elem[0]=key;//查找哨兵 for ( i=ST.length; ST.elem[i]!=key; –i ); return i; } SSTable creatST() { printf( “请输入数据的个数:” ); int n; do { scanf( “%d”,&n ); if ( n>0&&n<MAX_SIZE_ST ) break; printf( “数据不合法 请重新输入：” ); } while ( 1 ); SSTable ST; ST.elem=( ElemType * )malloc( MAX_SIZE_ST*sizeof( ElemType ) ); ST.length=n; printf( “请依次输入数值: ” ); for ( int i=1; i<=n; i++ ) { printf( “%d:”,i ); scanf( “%d”,ST.elem+i ); } printf( “顺序表建立完成! ” ); return ST; } int binary_find( SSTable ST,KeyType key ) { int low,high,mid; low=1; high=ST.length; while ( low<high ) { mid=( low +high )/2; if ( key==ST.elem[mid] ) return mid; else if ( key>ST.elem[mid] ) low=mid+1; else high=mid-1; } return 0; } int searchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if (!T) { p=f; return 0; } else if (key==T->data) { p=T; return 1; } else if (key<T->data) { return searchBST(T->lchild,key,T,p); } else return searchBST(T->rchild,key,T,p); } int insertBST(BiTree &T,ElemType e) { BiTree s,p; if ( !searchBST(T,e,NULL,p)) { s=new BiTNode(); s->data=e; s->lchild=s->rchild=NULL; if ( !p ) T=s; else if (e< p->data) p->lchild=s; else p->rchild=s; return 1; } else return 0; } BiTree creatBST(int n) { srand(time(NULL)); BiTree T=NULL,p; ElemType x; for ( int i=0; i<n; i++ ) { x=rand()%100; insertBST( T,x ); } return T; } BiTree Delete( BiTree &tptr,KeyType key ) { BiTree tmp,parent=NULL,p; p=tptr; while ( p ) { if ( p->data==key ) break; parent=p; p=( key<p->data )?p->lchild:p->rchild; } if ( !p ) return NULL; tmp=p; if ( !p->rchild&&!p->lchild ) { /*p的左右子树都为空*/ if ( !parent ) //要删根，须修改根指针 tptr=NULL; else if ( p==parent->rchild ) parent->rchild=NULL; else parent->lchild=NULL; free( p ); } else if ( !p->rchild ) { //p的右子树为空，则重接p的左子树 p=p->lchild; if ( !parent ) //要删根，须修改根指针 tptr=p; else if ( tmp==parent->lchild ) parent->lchild=p; else parent->rchild=p; free( tmp ); } else if ( !p->lchild ) { //的左子树为空，则重接p的左子树 p=p->rchild; if ( !parent ) //要删根，须修改根指针 tptr=p; else if ( tmp==parent->lchild ) parent->lchild=p; else parent->rchild=p; free( tmp ); } else if ( p->rchild&&p->lchild ) { //p有左子树和右子树，用p的后继覆盖p然后删去后继 //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树 parent=p; //由于用覆盖法删根，则不必特殊考虑删根 p=p->rchild; while ( p->lchild ) { parent=p; p=p->lchild; } tmp->data=p->data; if ( p==parent->lchild ) parent->lchild=NULL; else parent->rchild=NULL; free( p ); } return tptr; } void tree_display(BiTree T) { BiTree temp=T; if(temp) { tree_display(temp->lchild); printf(“%d “,temp->data); tree_display(temp->rchild); } } int main() { system( “color 0B” ); // 直接查找（未排序） SSTable ST=creatST(); printf( “请输入你要查找的数值: ” ); int s; scanf( “%d”,&s ); int i=search_seq(ST,s); if(!i)printf(“未找到 ”); else printf(“找到在第%d处 ”,i); //排序.二分法查找 sort( ST.elem+1,ST.elem+ST.length+1,cmp ); for ( int j=1; j<=ST.length; ++j ) printf( “%d “,*( ST.elem+j ) ); int j=binary_find( ST,s ); if ( !j )printf( “未找到！ ” ); else printf( “找到在第%d处！ ”,i ); //随机创建 二叉排序树 printf(“请输入结点的个数：”); int n; scanf(“%d”,&n); BiTree T; T=creatBST(n); printf(“创建完成 ”); tree_display(T); return 0; }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/45208.html
