二叉排序树

发布时间:2016-12-8 2:29:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"二叉排序树",主要涉及到二叉排序树方面的内容,对于二叉排序树感兴趣的同学可以参考一下。

学习二叉排序树时写的代码。 二叉排序树是一颗动态,是在动态的过程中生成的,不是一成不变的。 特点是:根节点左边的比根节点的值小,右边的值比根节点大,平均查找复杂度为O(log2*n); 用二维指针来建树,注意new node(),返回的是结构体指针。 #include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <map> #include <stack> using namespace std; typedef struct node { int data; struct node *left, *right; }bst, *Link; void inorder_print(Link L) { if(L != NULL) { inorder_print(L->left); printf("%d\n", L->data); inorder_print(L->right); } } void insert(Link *L, int key) { if(*L == NULL) { (*L) = new node(); (*L)->left = (*L)->right = NULL; (*L)->data = key; } else { if(key == (*L)->data) return ; else if(key < (*L)->data) insert(&(*L)->left, key); else insert(&(*L)->right, key); } } Link *Search(Link *L, int key) { if(*L) { if((*L)->data == key) return L; if(key < (*L)->data) return Search(&(*L)->left, key); else return Search(&(*L)->right, key); } return NULL; } Link Del(Link *L) { if((*L)->left != NULL) { Link fa, cur; fa = cur = (*L)->left; while(cur != NULL) { fa = cur; cur = cur->left; } (*L)->data = cur->data; if(fa != cur) fa->right = cur->left; else (*L)->left = cur->left; free(cur); } else { Link cur = (*L); (*L) = (*L)->right; free(cur); cur = NULL; } } void calmin(Link *L, int &ans) { Link p = (*L); ans = min(ans, p->data); while(p != NULL) { ans = min(ans, p->data); //printf("***%d\n", p->data); p = p->left; } } void calmax(Link *L, int &ans) { Link p = (*L); ans = max(ans, p->data); while(p != NULL) { ans = max(ans, p->data); //printf("***%d\n", p->data); p = p->right; } } int main() { Link L = NULL; for(;;) { printf("插入 查询 删除 遍历 最大值 最小值\n"); int q; scanf("%d", &q); int x; if(q == 1) { scanf("%d", &x); insert(&L, x); } else if(q == 2) { scanf("%d", &x); Link *Q = Search(&L, x); if(Q) printf("存在\n"); else printf("不存在\n"); } else if(q == 3) { scanf("%d", &x); Link *Q = Search(&L, x); if(!Q) printf("不存在\n"); else Del(Q); } else if(q == 4) { inorder_print(L); } else if(q == 5) { int ans = 0; calmax(&L, ans); printf("%d\n", ans); } else if(q == 6) { int ans = 100000000LL; calmin(&L, ans); printf("%d\n", ans); } } return 0; }  

上一篇:
下一篇:ecshop 模板与库文件lbi

相关文章

关键词: 二叉排序树

相关评论