【C++】2.3 二叉搜索树的实现

二叉搜索树左子树根右子树根根据需求不同等于的元素可能会被去重也可能会被留下这样查找一个数就可以只遍历一次数大选哪个右走小往左走查找效率ologn~on改进AVL树红黑树B树系列查找效率ologn模拟实现不多插入相同元素一Key结构1. 节点的定义代码语言javascriptAI代码解释templateclass K struct bsnode { K _key; bsnode* _left; bsnode* _right; bsnode(const K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} };2. 成员代码语言javascriptAI代码解释typedef bsnodeK node; node* _root nullptr;代码语言javascriptAI代码解释这样可以不用写构造函数3. 二叉树的插入代码语言javascriptAI代码解释bool insert(const K key) { if (_root nullptr) { _root new node(key); return 1; } node* cur _root; node* par nullptr; while (cur ! nullptr) { if (cur-_key key) { par cur; cur cur-_right; } else if (cur-_key key) { par cur; cur cur-_left; } else { return 0; } } node* newnode new node(key); if (par-_key key) { par-_right newnode; } else { par-_left newnode; } return 1; }方案定一个cur的指针当根节点小于插入元素向右走大于则向左走如果已经有这个数了则返回false如果cur为空则构造一个节点和cur最后一次经过的节点连接返回true那么cur已经指向空了怎么才能知道cur最后一次经过的节点在额外弄一个par指针尾随cur即可4. 树排序二叉搜索树的中序遍历左-中-右的特点为从小到大的数组因此可以中序遍历得到有序数组叫做树排序代码语言javascriptAI代码解释void inorder() { _inorder(_root); } void _inorder(node* root) { if (root nullptr)return; _inorder(root-_left); std::cout root-_key ; _inorder(root-_right); }5. 查找和插入同理但是要找的值大于节点向右走小于往左走代码语言javascriptAI代码解释bool find(const K _key) { node* cur _root; while (cur) { if (_key cur-_key) { cur cur-_left; } else if (_key cur-_key) { cur cur-_right; } else { return 1; } } return 0; }6. 删除重要删除的集中情况设删除节点的名称为MM子节点左右均空直接删除即可M子节点一个为空M父节点指向M的一个子节点再删除MM左右节点都为空 替换删除法将M节点用下面的节点交换再删除下面的数字节点 那么和哪个节点交换既可以做到快速删除又可以做到保持左子树根右子树根的性质呢 和左子树的最右节点最大节点或右子树的最左节点最小节点 1删除快速由于两个情况都是最左或最右节点因此一定满足删除方案1或2因此删除简单 2由于两个情况要么是小的最大要么是大的最小因此性质也是满足的 下面用右边最左来演示代码语言javascriptAI代码解释bool erase(const K _key) { node* par nullptr; node* cur _root; while (cur) { if (cur-_key key) { par cur; cur cur-_right; } else if (cur-_key key) { par cur; cur cur-_left; } else { if (cur-_left nullptr) { if (cur _root) { _root cur-_right; } else { if (par-_left cur) { par-_left cur-_right; } else { par-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { if (par-_left cur) { par-_left cur-_left; } else { par-_right cur-_left; } } delete cur; } else { node* rp cur; node* r cur-_right; while (r-_left) { rp r; r r-_left; } cur-_key r-_key; if (rp-_left r) { rp-_left r-_right; } else { rp-_right r-_right; } delete r; } return 1; } } return 0; }代码逻辑先找值为val的节点找不到返回0设找到的节点为M节点M左为空 1节点M为根节点直接将右节点设为根节点有没有右节点都无所谓 2M不为根节点 A.M为左节点M根节点连接M右节点删M