数据结构：查找子系统

1、/*题目：编写循序查找程序* 编写二分查找程序* 编写建立二叉排序树的程序* 编写在二叉排序树上的查找、输入、删除结点的程序* 编写二叉排序树的中序输出的程序* 设计一个选择式菜单，一级菜单形式如下：* 查 找 子 系 统* * * 1-顺 序 查找 * * 2-二 分 查找 * * 3-二叉排序树 * * 0-返 回 * * 请选择菜单号（0-3）：* 二叉排序树的二级菜单如下：* 二叉排序树* * * 1-更新二叉排序树 * * 2-查 找 结 点 * * 3-插 入 结 点 * * 4-删 除 结 点 * * 5-中序输出排序树 * * 0-返 回 * * 请选择菜单号（0-5）：*/#

2、include <stdio.h>#include <string.h>#include <stdlib.h>#define SEARCHMAX 30typedef struct node int trData; /根节点 struct node *lchild; /左子树 struct node *rchild; /右子树BtNode, *pBtNode;void seqSearch();void binSearch();void btSearch();pBtNode createBT();void searchBT(pBtNode T, int k);v

3、oid insBT(pBtNode *T, int k);void delBT(pBtNode *T, int k);void inorderBT(pBtNode T);void main() int choice, k = 1; while (k) printf("n 查 找 子 系 统n"); printf("*n"); printf("* 1-顺 序 查找 *n"); printf("* 2-二 分 查找 *n"); printf("* 3-二叉排序树 *n"); printf("

4、;* 0-返 回 *n"); printf("*n"); printf("请选择菜单号（0-3）："); fflush(stdin); scanf("%d", &choice); switch(choice) case 1: seqSearch(); break; case 2: binSearch(); break; case 3: btSearch(); break; case 0: k = 0; break; default: printf("输入错误，请重新输入。"); getchar()

5、; k = 1; break; void seqSearch() /顺序查找 int aSEARCHMAX, x, y, i; char ch; printf("建立一个整数的顺序表（以-1结束）："); for (i = 0; i<SEARCHMAX; i+) scanf("%d", &ai); getchar(); if (ai = -1) /记录结束位置，结束循环 y = i; break; printf("是否需要查找（Y/N）："); scanf("%c", &ch); while

6、(ch = 'y'|ch = 'Y') printf("请输入要查找的数据：n"); scanf("%d", &x); getchar(); i = 0; /找到数组的结束位置。 while (i < y-1&&ai != x) /找到要查找的数据的位置 i+; if (i = -1) /没找到 printf("对不起，没有找到。n"); else printf("该数据在第%d个位置上。n", i+1); printf("是否继续查找（Y/N

7、）："); scanf("%c", &ch); void binSearch() /二分查找 int bSEARCHMAX, i, y, x, low, mid, high, n; char ch; printf("建立递增有序的查找顺序表（以-1结束）：n"); for (i = 0; i<SEARCHMAX; i+) scanf("%d", &bi); getchar(); if (bi = -1) /记录结束位置，结束循环 y = i; break; printf("是否需要查找（Y/N

8、）："); scanf("%c", &ch); while (ch = 'y'|ch = 'Y') printf("请输入要查找的数据："); scanf("%d", &x); getchar(); low = 0; /低 high = y-1; /高 n = 0; /记录次数 while (low <= high) mid = (low+high)/2; n+; if (bmid > x) /在左边 high = mid-1; else if (bmid <

9、 x) /在右边 low = mid+1; else /找到 break; if (low > high) printf("对不起，没有找到该数据。n"); printf("共进行%d次比较。n", n); if (bmid < x) /查找最后小于该数据的位置 mid+; printf("可将此数据插入第个%d位置", mid+1); else printf("找到该数据在第%d个位置。n", mid+1); printf("共进行%d次比较。n", n); printf(&quo

10、t;是否需要查找（Y/N）："); scanf("%c", &ch); void btSearch() /二叉排序树 int choice, x, l = 1; pBtNode T; printf("建立一棵二叉排序树存储n"); T = createBT(); getchar(); while (l) printf("n 二叉排序树n"); printf("*n"); printf("* 1-更新二叉排序树 *n"); printf("* 2-查 找 结 点 *n&

11、quot;); printf("* 3-插 入 结 点 *n"); printf("* 4-删 除 结 点 *n"); printf("* 5-中序输出排序树 *n"); printf("* 0-返 回 *n"); printf("*n"); printf("请选择菜单号（0-5）："); fflush(stdin); scanf("%d", &choice); switch(choice) case 1: T = createBT(); brea

12、k; case 2: printf("请输入要查找的数据："); scanf("%d", &x); getchar(); searchBT(T, x); break; case 3: printf("请输入要插入的数据："); scanf("%d", &x); insBT(&T, x); break; case 4: printf("请输入要删除的数据："); scanf("%d", &x); delBT(&T, x); break;

13、case 5: inorderBT(T); break; case 0: l = 0; break; default: printf("输入错误，请重新输入。"); getchar(); l = 1; break; pBtNode createBT() /建立二叉树 pBtNode T; /声明指针 int x; T = NULL; printf("请输入一个整数（输入0结束）："); fflush(stdin); scanf("%d", &x); getchar(); while (x) /输入的数据非零时 insBT(&a

14、mp;T, x); /二叉树中插入数据 printf("请输入下一个整数（输入0结束）："); fflush(stdin); scanf("%d", &x); getchar(); return T; /返回指针void searchBT(pBtNode T, int k) /查找二叉树结点 pBtNode f = T; while (f) if(f->trData = k) /判断是否找到该数据 printf("已找到数据。n"); return; f = (k < f->trData )?f->lc

15、hild:f->rchild; /判断下一个查找的位置 printf("没有找到数据。n");void insBT(pBtNode *T, int k) /插入二叉树结点 pBtNode f, p; p = (*T); /指向指针的指针 while (p) /当结点不为空 if (p->trData = k) printf("树中已有%d，不需要插入。", k); return; else f = p; p = (k < p->trData)?p->lchild:p->rchild; /判断插入的数据的位置 p = (

16、BtNode *)malloc(sizeof(BtNode); /分配空间 p->trData = k; p->lchild = p->rchild = NULL; if (*T) = NULL) (*T) = p; else if (k<f->trData) f->lchild = p; else f->rchild =p; void delBT(pBtNode *T, int k) /删除二叉树结点 pBtNode p, q, child, parent = NULL; p = *T; while (p) /找到输入的数据的位置 if (p->

17、;trData = k) break; parent = p; /记录上一个结点 p = (k < p->trData)?p->lchild:p->rchild; if (!p) /没有找到位置 printf("没有找到你要删除的数据结点。n"); return; q = p; if (q->lchild&&q->rchild) for (parent = q, p = q->rchild; p->lchild; parent = p, p=p->lchild) ; child = (p->lchild)?p->lchild:p->rchild; /下一个指针的指向 if (!parent) *T = child; else if