代碼如下:

#include <iostream> using namespace std;struct BSTNode {double v = 0.0;BSTNode *lc = nullptr;BSTNode *rc = nullptr;BSTNode *par = nullptr; };void inorder_tree(BSTNode *t) {if (t != nullptr) {inorder_tree(t->lc);cout << t->v << " ";inorder_tree(t->rc);} }void preorder_tree(BSTNode *t) {if (t != nullptr) {cout << t->v << " ";preorder_tree(t->lc);preorder_tree(t->rc);} }void postorder_tree(BSTNode *t) {if (t != nullptr) {postorder_tree(t->lc);postorder_tree(t->rc);cout << t->v << " ";} }BSTNode *t_search_1(BSTNode *t, double k) {if (t == nullptr || k == t->v)return t;if (k < t->v)return t_search_1(t->lc, k);elsereturn t_search_1(t->rc, k); }BSTNode *t_search_2(BSTNode *t, double k) {while (t != nullptr && k != t->v) {if (k < t->v)t = t->lc;elset = t->rc;}return t; }BSTNode *t_min(BSTNode *t) {while (t->lc != nullptr)t = t->lc;return t; }BSTNode *t_max(BSTNode *t) {while (t->rc != nullptr)t = t->rc;return t; }BSTNode *t_successor(BSTNode *t) {BSTNode *y;if (t->rc != nullptr)return t_min(t->rc);y = t->par;while (y != nullptr && t == y->rc) {t = y;y = y->par;}return y; }BSTNode *t_predecessor(BSTNode *t) {BSTNode *y;if (t->lc != nullptr)return t_max(t->lc);y = t->par;while (y != nullptr && t == y->lc) {t = y;y = y->par;}return y; }void t_insert(BSTNode *&t, double w) {BSTNode *z;z = new BSTNode ;if (z == nullptr)return ;z->v = w;BSTNode *x = t;BSTNode *y = nullptr;while (x != nullptr) {y = x;if (z->v < x->v)x = x->lc;elsex = x->rc;}z->par = y;if (y == nullptr)t = z;else if (z->v < y->v)y->lc = z;elsey->rc = z; }void transplant(BSTNode *&t, BSTNode *u, BSTNode *v) {if (u->par == nullptr)t = v;else if (u->par->lc == u)u->par->lc = v;elseu->par->rc = v;if (v != nullptr)v->par = u->par; }BSTNode *t_delete_in(BSTNode *&t, BSTNode *z) {BSTNode *y = nullptr;if (z->lc == nullptr)transplant(t, z, z->rc);else if (z->rc == nullptr)transplant(t, z, z->lc);else {y = t_min(z->rc);if (y->par != z) {transplant(t, y, y->rc);y->rc = z->rc;y->rc->par = y;}transplant(t, z, y);y->lc = z->lc;y->lc->par = y;}return z; }void t_delete(BSTNode *&t, double w) {BSTNode *z, *node;z = t_search_2(t, w);if (z != nullptr) {node = t_delete_in(t, z);if (node != nullptr) {delete node;node = nullptr;}} }void t_destory(BSTNode *t) {if (t == nullptr)return ;if (t->lc != nullptr)return t_destory(t->lc);if (t->rc != nullptr)return t_destory(t->rc);delete t;t = nullptr; }int main() {int n;BSTNode *root;double *arr;cout << "請輸入節(jié)點/關(guān)鍵字個數(shù):" << endl;cin >> n;arr = new double [n];cout << "請依次輸入關(guān)鍵字(注意每棵子樹的根節(jié)點都要比它的孩子結(jié)點先輸入): " << endl;for (int i = 0; i < n; i++) {cin >> arr[i];t_insert(root, arr[i]);}cout << endl;cout << "二叉搜索樹先序遍歷的結(jié)果為: ";preorder_tree(root);cout << endl;cout << "二叉搜索樹中序遍歷的結(jié)果為: ";inorder_tree(root);cout << endl;cout << "二叉搜索樹后序遍歷的結(jié)果為: ";cout << endl;postorder_tree(root);cout << endl;double seakey;cout << "請輸入要查找的節(jié)點關(guān)鍵字:" << endl;cin >> seakey;cout << endl;BSTNode *seaNode = t_search_1(root, seakey);if (seaNode)cout << "查找成功!" << endl;elsecout << "查找失敗, 關(guān)鍵字為" << seakey << "的結(jié)點不存在" << endl;cout << endl;double delkey;cout << "請輸入要刪除的結(jié)點關(guān)鍵字: " << endl;cin >> delkey;cout << endl;t_delete(root, delkey);cout << "刪除操作后先序遍歷二叉搜索樹的結(jié)果為: ";preorder_tree(root);cout << endl;cout << "刪除操作后中序遍歷二叉搜索樹的結(jié)果為: ";inorder_tree(root);cout << endl;t_destory(root); // 銷毀二叉樹delete[] arr;system("pause");return 0; }

測試結(jié)果:

總結(jié)

以上是生活随笔為你收集整理的C++ struct结构体 实现搜索二叉树(BST)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。