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