二叉搜索树 - C++ 实现( 三 ) _生活百科

如果还是不太理解的话, 可以看看这个美国旧金山大学 CS 做的一个算法可视化. Binary Search Tree Visualization (usfca.edu) 在这个网站上详细地看到 BST 中每一步的操作. 做的很好, 不妨去玩玩!
代码实现 Implement下面的是 BST 类的完整实现.
class TreeNode{public: TreeNode(int m_data) : data(m_data) {} int data; TreeNode *left = nullptr; TreeNode *right = nullptr; TreeNode *parent = nullptr; bool isLeaf() {return left == nullptr && right == nullptr; }};class BinarySearchTree{public: void insert(const int item) {TreeNode *scan = root;TreeNode *prev = root;while (scan != nullptr){prev = scan;scan = item < scan->data ? scan->left : scan->right;}TreeNode *newNode = new TreeNode(item);if (root){(item < prev->data ? prev->left : prev->right) = newNode;newNode->parent = prev;}else{root = newNode;}return; } void remove(const int item) {TreeNode *delNode = p_find(item);if (delNode)p_remove(delNode); } void remove_ref(const int item) {TreeNode *&delNode = p_find_ref(item);if (delNode)p_remove_ref(delNode); } int find(const int item) {TreeNode *node = p_find(item);return node ? node->data : -1; } int pred(const int item) {TreeNode *node = p_pred(item);return node ? node->data : -1; } int succ(const int item) {TreeNode *node = p_succ(item);return node ? node->data : -1; } void print() {p_printAll(root);putchar('\n'); }private: TreeNode *root = nullptr; const TreeNode *empty = nullptr; void p_printAll(TreeNode *node) {if (!node)return;p_printAll(node->left);printf("%d ", node->data);p_printAll(node->right); } void p_remove(TreeNode *delNode) {if (delNode->isLeaf()) // case1{if (delNode->parent){// judge which pointer of node to modifyif (delNode == delNode->parent->left){delNode->parent->left = nullptr;}else{delNode->parent->right = nullptr;}}else // when root == delNode;{root = nullptr;}delete delNode;}else if (delNode->left == nullptr) // case 2{// basically same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->right;}else{delNode->parent->right = delNode->right;}}else // root == delNode;{root = delNode->right;root->parent = nullptr;}delete delNode;}else if (delNode->right == nullptr){// same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->left;}else{delNode->parent->right = delNode->left;}}else // root == delNode;{root = delNode->left;root->parent = nullptr;}delete delNode;}else{// case3TreeNode *succNode = p_succ(delNode);delNode->data = https://www.huyubaike.com/biancheng/succNode->data;p_remove(succNode);} } void p_remove_ref(TreeNode *&delNodeRef) {TreeNode *delPtr = delNodeRef;if (delNodeRef->isLeaf()){delNodeRef = nullptr;}else if (!delNodeRef->left || !delNodeRef->right){TreeNode *subTree = max(delNodeRef->right, delNodeRef->left);if (root == delNodeRef)subTree->parent = nullptr;delNodeRef = subTree;}else{TreeNode *succNode = p_succ(delNodeRef);delNodeRef->data = succNode->data;p_remove(succNode);}delete delPtr; } TreeNode *p_find(const int item) {TreeNode *scan = root;while (scan != nullptr && scan->data != item){scan = item < scan->data ? scan->left : scan->right;}return scan; } TreeNode *&p_find_ref(const int item) {TreeNode *scan = root;TreeNode *prev = nullptr;while (scan != nullptr && scan->data != item){prev = scan;scan = item < scan->data ? scan->left : scan->right;}if (root->data == item) return root;if (!scan) return (TreeNode *&) empty;return prev->left == scan ? (*prev).left : (*prev).right; } TreeNode *p_pred(int item) {TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->left){return p_max(itemNode->left);}else{TreeNode *scan = itemNode->parent;while (scan && scan->left == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_succ(int item) {TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_succ(TreeNode *itemNode) {if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_max(TreeNode *node) {if (!node)return nullptr;while (node->right){node = node->right;}return node; } TreeNode *p_min(TreeNode *node) {if (!node)return nullptr;while (node->left){node = node->left;}return node; }};结构分析 Analysis总结上文提到的所有操作, 对 BST 的每一步操作都是向树的深处再进一层, 而每一次进入一颗子树都意味着筛选掉了当前树中的一半节点, 对剩下来的一半节点继续操作.(二分思想)
由此, 我们可以容易的的得到一个结论: BST 中的最大查找次数取决于 BST 的最大深度, 即树高. 在最好情况下, 一个有着 n 个节点的树, 他的深度最小为 \(\log_2 n\). 此时, BST 可以达到最高效率.

二叉搜索树 - C++ 实现( 三 )

推荐阅读

花高额费用存脐带血储存一般多少钱

王者荣耀背景修改，王者荣耀实名制弄错了怎么修改？，

这个肉是什么肉这个多肉是什么

国漫天官赐福让原著粉丝飘了，你认为是尬捧还是真的好看？

都江堰市2023年小升初入学指南都江堰市小升初招生网

联想手机怎么使用手写输入法

宁夏理工学院2022年分省分专业招生计划(本科+专科）

良心建议，双子座如何过好单身生活

描写柳树的诗句碧玉妆成一树高万条垂下绿丝绦

冷冻的面包吃的时候应该怎么处理冷冻的面包吃的时候应该怎么处理呢

请使用微信内浏览器登录什么意思

淘宝技巧步骤如下，淘宝天猫运营流程及规划？

粽子中腌肉方子肉粽子的肉怎么腌制

冬至可不可以晒衣服冬至可以晒衣服吗

白牡丹多肉植物的种植方法

冬枣一天吃几个比较好冬枣一天吃多少比较好

北京天马旅行社有限公司_工商信用信息_经营范围期限状态_法人_地址_注册资本_怎么样

双子座男神养成计划

雷颂德名字打分106分

巨蟹座跟处女座配吗