数据结构：查找子系统

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

2、include #include #include #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);void insBT(pBtNode *T, int k);void delBT(pBtNode

3、 *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(* 0-返 回 *n); printf(*n); printf(请选择菜单号（0-3）：); fflush(stdin); scanf(%d, &choice); switch(choice) case 1: seqSear

4、ch(); break; case 2: binSearch(); break; case 3: btSearch(); break; case 0: k = 0; break; default: printf(输入错误，请重新输入。); getchar(); k = 1; break; void seqSearch() /顺序查找 int aSEARCHMAX, x, y, i; char ch; printf(建立一个整数的顺序表（以-1结束）：); for (i = 0; iSEARCHMAX; i+) scanf(%d, &ai); getchar(); if (ai = -1) /记

5、录结束位置，结束循环 y = i; break; printf(是否需要查找（Y/N）：); scanf(%c, &ch); while (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）：); scanf(%c, &ch); vo

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

7、ar(); low = 0; /低 high = y-1; /高 n = 0; /记录次数 while (low x) /在左边 high = mid-1; else if (bmid high) printf(对不起，没有找到该数据。n); printf(共进行%d次比较。n, n); if (bmid trData = k) /判断是否找到该数据 printf(已找到数据。n); return; f = (k trData )?f-lchild:f-rchild; /判断下一个查找的位置 printf(没有找到数据。n);void insBT(pBtNode *T, int k) /插入二

8、叉树结点 pBtNode f, p; p = (*T); /指向指针的指针 while (p) /当结点不为空 if (p-trData = k) printf(树中已有%d，不需要插入。, k); return; else f = p; p = (k trData)?p-lchild:p-rchild; /判断插入的数据的位置 p = (BtNode *)malloc(sizeof(BtNode); /分配空间 p-trData = k; p-lchild = p-rchild = NULL; if (*T) = NULL) (*T) = p; else if (ktrData) f-lch

9、ild = p; else f-rchild =p; void delBT(pBtNode *T, int k) /删除二叉树结点 pBtNode p, q, child, parent = NULL; p = *T; while (p) /找到输入的数据的位置 if (p-trData = k) break; parent = p; /记录上一个结点 p = (k 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 (p = parent-lchild) parent-lchild = child; else parent-rchild = child; if