实现二叉排序树建立和检索算法(C语言)【急求】
#include #include #include #define INFMT "%d" #define OUTFMT "%d " /* #define NULL 0L */ #define BOOL int #define TRUE 1 #define FALSE 0 #define LEN 10000 typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild, *rchild; } BSTNode, *BSTree; /* 插入新节点 *...全部
#include #include #include #define INFMT "%d" #define OUTFMT "%d " /* #define NULL 0L */ #define BOOL int #define TRUE 1 #define FALSE 0 #define LEN 10000 typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild, *rchild; } BSTNode, *BSTree; /* 插入新节点 */ void Insert(BSTree *tree, ElemType item) { BSTree node = (BSTree)malloc(sizeof(BSTNode)); node->data = item; node->lchild = node->rchild = NULL; if (!*tree) *tree = node; else { BSTree cursor = *tree; while (1) { if (item data) { if (NULL == cursor->lchild) { cursor->lchild = node; break; } cursor = cursor->lchild; } else { if (NULL == cursor->rchild) { cursor->rchild = node; break; } cursor = cursor->rchild; } } } return; } /* 查找指定值 */ BSTree Search(BSTree tree, ElemType item) { BSTree cursor = tree; while (cursor) { if (item == cursor->data) return cursor; else if ( item data) cursor = cursor->lchild; else cursor = cursor->rchild; } return NULL; } /* 中缀遍历 */ void Inorder(BSTree tree) { BSTree cursor = tree; if (cursor) { Inorder(cursor->lchild); printf(OUTFMT, cursor->data); Inorder(cursor->rchild); } } /* 回收资源 */ void Cleanup(BSTree tree) { BSTree cursor = tree, temp = NULL; if (cursor) { Cleanup(cursor->lchild); Cleanup(cursor->rchild); free(cursor); } } /* 产生一组随机数 */ void randnum(int *a, int s) { int i, j, mod = s * 10; srand(time(NULL)); for (i = 0; i { a[i] = rand() % mod 1; for (j = 0; j { if (a[i] == a[j]) { a[i] = rand() % mod 1; j = -1; continue; } } } } void main() { ElemType item; char choice; BSTree root = NULL, ret; /* 必须赋予NULL值,否则出错 */ BOOL finish = FALSE; printf("***欢迎使用二叉排序树演示程序***
"); printf("请选择创建树的方式:
"); printf("1。
手动输入数据创建二叉排序树
"); printf("2。 自动产生数据创建二叉排序树
"); do { scanf("%c", &choice); getchar(); if (choice == '1' || choice == '2') finish = TRUE; } while (FALSE == finish); switch (choice) { case '1': { printf("请输入数据(-10000结束):
"); while (1) { scanf(INFMT, &item); if (-10000 != item) Insert(&root, item); else break; } break; } case '2': { int ia[LEN], i = 0, loop = LEN; randnum(ia, LEN); while (loop--) { Insert(&root, ia[i ]); } break; } } printf("
创建完成。
。。
"); Inorder(root); printf("
"); /* 二叉排序树的查找测试 */ do { printf("
请输入查找数据:"); scanf("%d", &item); getchar(); printf("Searching。
。。
"); ret = Search(root, item); if (NULL == ret) printf("查找失败!"); else printf("查找成功!"); printf("
继续测试按y,退出按其它键。
"); choice = getchar(); } while (choice=='y'||choice=='Y'); Cleanup(root); }。收起