二叉排序树遍历&二叉树打印&简单图书管理系统
2021/12/29 6:08:48
本文主要是介绍二叉排序树遍历&二叉树打印&简单图书管理系统,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<math.h> #include<vector> #include<iostream> #include<time.h> using namespace std; constexpr auto ARRAY_INIT_SIZE = 100; // 栈存储空间初始分配量 constexpr auto STACK_INIT_SIZE = 100; // 栈存储空间初始分配量 constexpr auto STACKINCREMENT = 10; // 栈存储空间分配增量 constexpr auto QUENE_INIT_SIZE = 100; // 队列存储空间初始分配量 constexpr auto QUENEINCREMENT = 10; // 队列存储空间分配增量 typedef struct Node { int data; Node* Ltree; Node* Rtree; }*NTree; // 定义栈 typedef struct Stack { Node* base; Node* top; int stacksize; }; typedef struct IntStack { int* base; int* top; int stacksize; }; //定义队列 typedef struct Quene { NTree arr[QUENE_INIT_SIZE]; int length; int quenesize; }; typedef struct child { NTree tree; int serial; }; // 队列 typedef struct quene { child arr[QUENE_INIT_SIZE]; int length; int quenesize; }; typedef struct Date { int Y, M, D; }; typedef struct { //编号 书名 作者 价格 购买时间 int id; string name, author, price; Date buyingtime; }Book, Datatype; typedef struct BNode { Datatype book; BNode* Ltree; BNode* Rtree; }*BTree; //声明函数 void InitStack(Stack&); void Push(Stack&, Node*); void Pop(Stack&, Node&); Node getTop(Stack); void PreOrderTraverse(NTree); //非递归先序遍历 void InOrderTraverse(NTree); //非递归中序遍历 void PostOrderTraverse(NTree); //非递归后序遍历 NTree Root(); void insert(NTree, int); void Treeinput(vector<int>&); void add(Quene); NTree Pop(Quene); void add(quene*&, NTree, int, int); int Pop(quene); quene* LevelTraversal(NTree); //层次遍历 void Treeprint(quene*); //二叉树打印 class ArrayLMS { public: // 功能记录项 int lion = 99; int current_date; ArrayLMS(); //~ArrayLMS(); //查询操作 Book Search(); //插入操作 void Insert(); //更新操作 int Update(); private: Book* A; Book* InitBArray(); void gettime(); void Bookshow(Book b); void Insert(Book*& a, Book n); void Table() { cout << "------------------------------------\n"; cout << "-------简单图书管理系统(数组)-----\n"; cout << "------------1: 图书检索-------------\n"; cout << "------------2: 图书插入-------------\n"; cout << "------------3: 图书修改-------------\n"; cout << "---------------0: 退出--------------\n"; cout << "------------------------------------\n"; } }; class TreeLMS { public: // 功能记录项 int lion = 99; int current_date; TreeLMS(); //~TreeLMS(); //查询操作 Book Search(); //插入操作 void Insert(); //更新操作 int Update(); private: BTree T; void gettime(); BTree InitBTree(); void Treeinput(vector<Book>& v); void Bookshow(Book b); void Insert(BTree& t, Book n); void Table() { cout << "------------------------------------\n"; cout << "-----简单图书管理系统(二叉树)-----\n"; cout << "------------1: 图书检索-------------\n"; cout << "------------2: 图书插入-------------\n"; cout << "------------3: 图书修改-------------\n"; cout << "---------------0: 退出--------------\n"; cout << "------------------------------------\n"; } #include"标头.h" void main() { //任务一 编辑生成排序二叉树 NTree T = Root(); vector<int> v; Treeinput(v); for (int i = 0; i < v.size(); i++) { insert(T, v[i]); } //任务二 //非递归前序 cout << "非递归前序遍历:"; PreOrderTraverse(T); //非递归中序 cout << "\n非递归中序遍历:"; InOrderTraverse(T); cout << "\n非递归后序遍历:"; //非递归后序 PostOrderTraverse(T); //任务三 //层次遍历 cout << "\n层次遍历:"; quene* q = LevelTraversal(T); //二叉树打印 Treeprint(q); cout << "\n"; //任务四.1 二叉排序树简单图书管理系统 TreeLMS t; while (t.lion) { cout << "----------请输入功能编号----------\n"; cin >> t.lion; switch (t.lion) { case 1:t.Search(); break; case 2:t.Insert(); break; case 3:t.Update(); break; case 0:cout << "-----------系统退出-----------\n"; break; default:printf("-----------输入错误-----------\n"); break; } } //任务四.2 数组简单图书管理系统 ArrayLMS a; while (a.lion) { cout << "----------请输入功能编号----------\n"; cin >> a.lion; switch (a.lion) { case 1:a.Search(); break; case 2:a.Insert(); break; case 3:a.Update(); break; case 0:cout << "-----------系统退出-----------\n"; break; default:printf("-----------输入错误-----------\n"); break; } } } NTree Root(){ NTree t = (NTree)malloc(sizeof(Node)); t->data = NULL; t->Ltree = NULL; t->Rtree = NULL; return t; } void insert(NTree t, int n) { if (t->data == NULL) { t->data = n; return; } NTree tmp, p; p = t; tmp = (NTree)malloc(sizeof(Node)); tmp->data = n; tmp->Ltree = NULL; tmp->Rtree = NULL; while(p){ if (p->data == n) { return; } if (p->data < n) { if (p->Rtree) { p = p->Rtree; continue; } else { p->Rtree = tmp; return; } } if (p->data > n) { if (p->Ltree) { p = p->Ltree; continue; } else { p->Ltree = tmp; return; } } } } void Treeinput(vector<int> &v) { int tmp = 0; cout << "请输入整形个数" << endl; int num; cin >> num; for (int i = 0; i < num; i++) { cout << "请输入第" << i + 1 << "个整形元素"<<endl; cin >> tmp; v.push_back(tmp); } } //栈初始化 void InitStack(Stack& S) { S.base = (Node*)malloc(sizeof(Node) * STACK_INIT_SIZE); S.top = S.base; S.stacksize = STACK_INIT_SIZE; } void InitStack(IntStack& S) { S.base = (int*)malloc(sizeof(int) * STACK_INIT_SIZE); S.top = S.base; S.stacksize = STACK_INIT_SIZE; } // 入栈 void Push(Stack& S, Node* t) { if (S.top - S.base >= S.stacksize) { S.base = (Node*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(Node)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = *t; } void Push(IntStack& S, int t) { if (S.top - S.base >= S.stacksize) { S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = t; } //获取栈顶 Node getTop(Stack S) { return *(S.top - 1); } // 出栈 void Pop(Stack& S, Node& t) { if (S.top != S.base) { t = *(--S.top); } } int Pop(IntStack& S) { if (S.top != S.base) { return *(--S.top); } } // 非递归先序遍历 void PreOrderTraverse(Node* T) { if (!T) return; Stack S; InitStack(S); Node p; p = *T; Push(S, &p); while (S.top != S.base) { Pop(S, p); cout << p.data << "->"; if (p.Rtree) { Push(S, p.Rtree); } if (p.Ltree) { Push(S, p.Ltree); } } } // 非递归中序遍历 void InOrderTraverse(NTree T) { Stack S; InitStack(S); Node c = *T; Node* p = &c; while (S.top != S.base || p) { if (p) { Push(S, p); p = p->Ltree; } else { Node tmp; Pop(S, tmp); p = &(tmp); if (p->data == '#')return; cout << p->data << "->"; p = p->Rtree; } } } // 非递归后序遍历 void PostOrderTraverse(NTree T) { if (T == NULL) return; // 结点栈 Stack S; // 状态栈 IntStack O; InitStack(S); InitStack(O); Node tmp = *T; Node* p = &tmp; //状态变量 int tag = 0; Push(S, p); Push(O, 0); p = p->Ltree; while (S.top != S.base) { if (p) { Push(S, p); Push(O, 0); p = p->Ltree; } else { tag = Pop(O); if (!tag) { Push(O, 1); tmp = getTop(S); p = &tmp; p = p->Rtree; } else { tmp = getTop(S); cout << tmp.data << "->"; Pop(S, tmp); } } } } void add(Quene* &q,NTree t){ if (q->length >= q->quenesize) { q = (Quene*)realloc(q, q->quenesize + QUENEINCREMENT * sizeof(Quene)); q->quenesize += QUENEINCREMENT; } q->arr[q->length++] = t; } void add(quene*& q, NTree t, int n, int order) { /// <param name="q"></队列> /// <param name="t"></树> /// <param name="n"></类型> /// <param name="order"></父节点序号> if (q->length >= q->quenesize) { q = (quene*)realloc(q, q->quenesize + QUENEINCREMENT * sizeof(quene)); q->quenesize += QUENEINCREMENT; } q->arr[q->length].tree = t; //add左孩子 if (n == 0) { q->arr[q->length].serial = 2 * order + 1; } //add右孩子 if (n == 1) { q->arr[q->length].serial = 2 * order + 2; } q->length++; } NTree Pop(Quene* &q) { NTree tmp = q->arr[0]; for (int i = 0; i < q->length;i++) { q->arr[i] = q->arr[i + 1]; } q->length--; return tmp; } NTree Search(quene*& q, int n) { NTree tmp = q->arr[n].tree; return tmp; } int Order(quene*& q, int n) { return q->arr[n].serial; } quene* LevelTraversal(NTree t) { //层次遍历二叉树,返回二叉树的队列形式 // Quene* q = (Quene*)malloc(sizeof(Quene) * QUENE_INIT_SIZE); quene* r = (quene*)malloc(sizeof(quene) * QUENE_INIT_SIZE); NTree tmp; int n = 0; int order; q->length = 0; q->quenesize = QUENE_INIT_SIZE; r->length = 0; r->quenesize = QUENE_INIT_SIZE; add(q, t); //r->arr[0] = (child*)malloc(quene) r->arr[0].tree = t; r->arr[0].serial = 0; r->length++; while (q->length != 0) { tmp = Pop(q); order = Order(r, n); n++; if (tmp->Ltree) { add(q, tmp->Ltree); add(r, tmp->Ltree, 0, order); } if (tmp->Rtree) { add(q, tmp->Rtree); add(r, tmp->Rtree, 1, order); } cout << tmp->data << "->"; } cout << endl; return r; } void Treeprint(quene* q) { //第i-1行的最左侧空格数为2 ** (layers - i) - 1 行内元素空格数为 2 * (layers + 1 - i) -1 int length = q->length; int layers = floor(log(q->arr[length - 1].serial + 1) / log(2)); //换行标识 打印最左侧空格数标识 int mark = 1; for (int i = 0; i < length; i++) { // 每一层最左侧结点 2**i -1 // 换行判断 if (floor(log(q->arr[i].serial + 1) / log(2)) != floor(log(q->arr[i - 1].serial + 1) / log(2)) && i != 0) { cout << endl; mark = 1; } float row = log(q->arr[i].serial + 1) / log(2); if (int(row) == row) { for (int j = 0; j < pow(2, (layers - int(row))) - 1; j++) { cout << " "; } cout << Search(q, i)->data; mark = 0; continue; } else { if (mark) { for (int j = 0; j < pow(2, (layers - int(row) + 1)) * (q->arr[i].serial - pow(2, (int)row - 1)) + pow(2, (layers - int(row))) - 1; j++) { cout << " "; } // 每一层最右侧结点 2**i -2 cout << Search(q, i)->data; mark = 0; } else { for (int j = 0; j < pow(2, (layers - int(row) + 1)) * (q->arr[i].serial - q->arr[i - 1].serial) - 1; j++) { cout << " "; } // 每一层最右侧结点 2**i -2 cout << Search(q, i)->data; } } } } #include"标头.h" BTree TreeLMS::InitBTree() { //BTree t = (BTree)malloc(sizeof(BNode)); 错误 由于string不定长 使用malloc不能动态分配内存 BTree t = new BNode; t->book.id = NULL; t->Ltree = t->Rtree = NULL; return t; } TreeLMS::TreeLMS() { T = InitBTree(); vector<Book> v; Book tmp1, tmp2, tmp3; tmp1.id = 50; tmp1.name = "时间简史"; tmp1.author = "霍金"; tmp1.price = 55; tmp1.buyingtime.Y = 2019; tmp1.buyingtime.M = 9; tmp1.buyingtime.D = 1; tmp2.id = 29; tmp2.name = "机器学习"; tmp2.author = "周志华"; tmp2.price = 77; tmp2.buyingtime.Y = 2018; tmp2.buyingtime.M =8; tmp2.buyingtime.D = 4; tmp3.id = 31; tmp3.name = "数学模型"; tmp3.author = "姜启源"; tmp3.price = 90; tmp3.buyingtime.Y = 2017; tmp3.buyingtime.M = 5; tmp3.buyingtime.D = 17; Insert(T, tmp1); Insert(T, tmp2); Insert(T, tmp3); Table(); } void TreeLMS::Treeinput(vector<Book>& v) { Book tmp; cout << "请输入录入书籍数" << endl; int num; cin >> num; for (int i = 0; i < num; i++) { cout << "请输入第" << i + 1 << "本书的编号 书名 作者 价格 购买时间" << endl; cin >> tmp.id>> tmp.name>> tmp.author>> tmp.price >> tmp.buyingtime.Y>> tmp.buyingtime.M>> tmp.buyingtime.D; v.push_back(tmp); } } void TreeLMS::Insert(BTree &t, Book n) { if (!t->book.id) { t->book = n; return; } BTree tmp, p; p = t; tmp = new BNode; tmp->book = n; tmp->Ltree = NULL; tmp->Rtree = NULL; while (p) { if (p->book.id == n.id) { return; } if (p->book.id < n.id) { if (p->Rtree) { p = p->Rtree; continue; } else { p->Rtree = tmp; return; } } if (p->book.id > n.id) { if (p->Ltree) { p = p->Ltree; continue; } else { p->Ltree = tmp; return; } } } } void TreeLMS::Insert() { Book n; cout << "----------请输入录入书籍的编号 书名 作者 价格 购买时间----------" << endl; cin >> n.id >> n.name >> n.author >> n.price >> n.buyingtime.Y >> n.buyingtime.M >> n.buyingtime.D; if (T->book.id) { T->book = n; return; } BTree tmp, p; p = T; tmp = (BTree)malloc(sizeof(BNode)); tmp->book = n; tmp->Ltree = NULL; tmp->Rtree = NULL; while (p) { if (p->book.id == n.id) { return; } if (p->book.id < n.id) { if (p->Rtree) { p = p->Rtree; continue; } else { p->Rtree = tmp; return; } } if (p->book.id > n.id) { if (p->Ltree) { p = p->Ltree; continue; } else { p->Ltree = tmp; return; } } } } Book TreeLMS::Search() { cout << "--------请输入检索书籍的ID--------" << endl; int id; cin >> id; BTree t = T; if (!t->book.id) { cout << "-----------图书库为空-----------" << endl; return t->book; } while (t) { if (t->book.id < id) { t = t->Rtree; continue; } if (t->book.id > id) { t = t->Ltree; continue; } if (t->book.id == id) { Bookshow(t->book); return t->book; } } cout << "-----------图书库无收录-----------" << endl; return t->book; } int TreeLMS::Update() { cout << "--------请输入更新书籍的ID--------" << endl; int id; cin >> id; BTree t = T; if (!t->book.id) { cout << "-----------图书库为空-----------" << endl; return 0; } while (t) { if (t->book.id < id) { t = t->Rtree; continue; } if (t->book.id > id) { t = t->Ltree; continue; } if (t->book.id == id) { Bookshow(t->book); int c = 99; while(c){ cout << "--------请输入更新书籍的信息类别--------" << endl; cout << "--------编号:1 书名:2 作者:3 价格:4 购买时间:5--------" << endl; cout << "-------------结束请输入:0---------------" << endl; cin >> c; switch (c) { case 1: cout << "--------请输入更新书籍的编号--------" << endl; cin >> t->book.id; break; case 2: cout << "--------请输入更新书籍的书名--------" << endl; cin >> t->book.name; break; case 3: cout << "--------请输入更新书籍的作者--------" << endl; cin >> t->book.author; break; case 4: cout << "--------请输入更新书籍的价格--------" << endl; cin >> t->book.price; break; case 5: cout << "------请输入更新书籍的购买时间------" << endl; cin >> t->book.buyingtime.Y >> t->book.buyingtime.M >> t->book.buyingtime.D; break; default: cout << "----------------结束----------------" << endl; break; } } return 1; } } cout << "-----------图书库无此书-----------" << endl; return 0; } void TreeLMS::Bookshow(Book b) { cout << "ID: " << b.id << " ,书名:" << b.name << " ,作者:" << b.author << " ,作者:" << b.author << " ,购买时间:" << b.buyingtime.Y << "-" << b.buyingtime.M << "-" << b.buyingtime.D << endl; } ArrayLMS::ArrayLMS() { A = InitBArray(); Book tmp1, tmp2, tmp3; tmp1.id = 50; tmp1.name = "时间简史"; tmp1.author = "霍金"; tmp1.price = 55; tmp1.buyingtime.Y = 2019; tmp1.buyingtime.M = 9; tmp1.buyingtime.D = 1; tmp2.id = 29; tmp2.name = "机器学习"; tmp2.author = "周志华"; tmp2.price = 77; tmp2.buyingtime.Y = 2018; tmp2.buyingtime.M = 8; tmp2.buyingtime.D = 4; tmp3.id = 31; tmp3.name = "数学模型"; tmp3.author = "姜启源"; tmp3.price = 90; tmp3.buyingtime.Y = 2017; tmp3.buyingtime.M = 5; tmp3.buyingtime.D = 17; Insert(A, tmp1); Insert(A, tmp2); Insert(A, tmp3); Table(); } Book ArrayLMS::Search() { cout << "--------请输入检索书籍的ID--------" << endl; int id; cin >> id; if (!A[0].id) { cout << "-----------图书库为空-----------" << endl; return A[0]; } for (int i = 0; i < ARRAY_INIT_SIZE; i++) { if (A[i].id == id) { Bookshow(A[i]); return A[i]; } } cout << "-----------图书库无收录-----------" << endl; return A[99]; } Book* ArrayLMS::InitBArray() { Book* a = new Book[ARRAY_INIT_SIZE]; for (int i = 0; i < ARRAY_INIT_SIZE; i++) { a[i].id = 0; } return a; } void ArrayLMS::Insert(Book*& a, Book n) { for (int i = 0; i < ARRAY_INIT_SIZE; i++) { if (!a[i].id) { a[i] = n; break; } } } void ArrayLMS::Insert() { Book n; cout << "----------请输入录入书籍的编号 书名 作者 价格 购买时间----------" << endl; cin >> n.id >> n.name >> n.author >> n.price >> n.buyingtime.Y >> n.buyingtime.M >> n.buyingtime.D; for (int i = 0; i < ARRAY_INIT_SIZE; i++) { if (!A[i].id) { A[i] = n; break; } } } int ArrayLMS::Update() { cout << "--------请输入更新书籍的ID--------" << endl; int id; cin >> id; for (int i = 0; i < ARRAY_INIT_SIZE; i++) { if (A[i].id == id) { Bookshow(A[i]); int c = 99; while (c) { cout << "--------请输入更新书籍的信息类别--------" << endl; cout << "--------编号:1 书名:2 作者:3 价格:4 购买时间:5--------" << endl; cout << "-------------结束请输入:0---------------" << endl; cin >> c; switch (c) { case 1: cout << "--------请输入更新书籍的编号--------" << endl; cin >> A[i].id; break; case 2: cout << "--------请输入更新书籍的书名--------" << endl; cin >> A[i].name; break; case 3: cout << "--------请输入更新书籍的作者--------" << endl; cin >> A[i].author; break; case 4: cout << "--------请输入更新书籍的价格--------" << endl; cin >> A[i].price; break; case 5: cout << "------请输入更新书籍的购买时间------" << endl; cin >> A[i].buyingtime.Y >> A[i].buyingtime.M >> A[i].buyingtime.D; break; default: cout << "----------------结束----------------" << endl; break; } } } } return 1; } void ArrayLMS::Bookshow(Book b) { cout << "ID: " << b.id << " ,书名:" << b.name << " ,作者:" << b.author << " ,作者:" << b.author << " ,购买时间:" << b.buyingtime.Y << "-" << b.buyingtime.M << "-" << b.buyingtime.D << endl; } };
这篇关于二叉排序树遍历&二叉树打印&简单图书管理系统的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求