南京网站设计制作套餐音乐网页设计材料加字加图片

南京网站设计制作套餐,音乐网页设计材料加字加图片,wordpress 热门排序,网站公司的利润二叉搜索树左子树根#xff0c;右子树根根据需求不同#xff0c;等于的元素可能会被去重也可能会被留下这样查找一个数就可以只遍历一次#xff0c;数大选哪个右走#xff0c;小往左走查找效率#xff1a;ologn~on改进#xff1a;AVL树#xff0c;红黑树#x…二叉搜索树左子树根右子树根根据需求不同等于的元素可能会被去重也可能会被留下这样查找一个数就可以只遍历一次数大选哪个右走小往左走查找效率ologn~on改进AVL树红黑树B树系列查找效率ologn模拟实现不多插入相同元素一Key结构1. 节点的定义templateclass K struct bsnode { K _key; bsnode* _left; bsnode* _right; bsnode(const K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} };2. 成员typedef bsnodeK node; node* _root nullptr;这样可以不用写构造函数3. 二叉树的插入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. 树排序二叉搜索树的中序遍历左-中-右的特点为从小到大的数组因此可以中序遍历得到有序数组叫做树排序void inorder() { _inorder(_root); } void _inorder(node* root) { if (root nullptr)return; _inorder(root-_left); std::cout root-_key ; _inorder(root-_right); }5. 查找和插入同理但是要找的值大于节点向右走小于往左走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由于两个情况要么是小的最大要么是大的最小因此性质也是满足的下面用右边最左来演示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右节点删MB.M为右节点M根节点连接M右节点删M节点M右为空同上1节点M为根节点直接将左节点设为根节点2M不为根节点A.M为左节点M根节点连接M左节点删MB.M为右节点M根节点连接M左节点删MM左右都不为空即else先去寻找右子树的最左节点设为rr的父节点设为rp由于r为最左节点因此左边不会有子节点1正常情况r为rp左节点交换r和M的值再删r节点连rp和r子节点2反常情况M的子节点只有右节点此时M就是rpr为rp右节点和正常情况恰好相反交换r和M的值再删r节点连rp和r子节点二Key-value结构由于二叉树不一定每一个成员代表的都是1因此用value记录数值所有程序和key结构一样只是模板节点构造函数多了value而已templateclass K,class V struct bsnode { K _key; V _val; bsnode* _left; bsnode* _right; bsnode(const K key,const V val) :_key(key) ,_val(val) ,_left(nullptr) ,_right(nullptr) { } };三构造析构函数1. 前序遍历拷贝构造先拷贝值再拷贝子节点由于拷贝构造无法递归因此先写前序遍历再复用递归函数node* copy(node* root) { if (root nullptr)return nullptr; node* newroot new node(root-_key, root-_val); newroot-_left copy(root-_left); newroot-_right copy(root-_right); return newroot; }拷贝构造bstree(const bstree t) { _root copy(t._root); }由于写了拷贝构造就不会生成默认构造因此强制生成bstree() default;2. 后序析构函数先析构子节点再析构自身由于析构无法递归因此先写前序遍历再复用void destroy(node*root) { if (rootnullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; } ~bstree() { destroy(_root); _root nullptr; }3. 赋值重载现代写法直接交换再销毁原来的bstreeoperator(bstree t) { std::swap(_root, t._root); return *this; }代码#includeiostream #includeassert.h namespace key { templateclass K struct bsnode { K _key; bsnode* _left; bsnode* _right; bsnode(const Kkey) :_key(key ) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K class bstree { public: typedef bsnodeK node; 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; } void inorder() { _inorder(_root); } //bool find(const K val) //{ // node* cur _root; //} bool find(int _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; } bool erase(int 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; } private: void _inorder(node* root) { if (root nullptr)return; _inorder(root-_left); std::cout root-_key ; _inorder(root-_right); } node* _root nullptr; }; } namespace key_value { templateclass K,class V struct bsnode { K _key; V _val; bsnode* _left; bsnode* _right; bsnode(const K key,const V val) :_key(key) ,_val(val) , _left(nullptr) , _right(nullptr) { } }; templateclass K,class V class bstree { public: typedef bsnodeK,V node; bstree(const bstree t) { _root copy(t._root); } bstree() default; bstreeoperator(bstree t) { std::swap(_root, t._root); return *this; } bool insert(const K key, const V val) { if (_root nullptr) { _root new node(key,val); 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,val); if (par-_key key) { par-_right newnode; } else { par-_left newnode; } return 1; } void inorder() { _inorder(_root); } //bool find(const K val) //{ // node* cur _root; //} node* 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 cur; } } return nullptr; } 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; cur-_val r-_val; if (rp-_left r) { rp-_left r-_right; } else { rp-_right r-_right; } delete r; } return 1; } } return 0; } ~bstree() { destroy(_root); _root nullptr; } private: node* copy(node* root) { if (root nullptr)return nullptr; node* newroot new node(root-_key, root-_val); newroot-_left copy(root-_left); newroot-_right copy(root-_right); return newroot; } void _inorder(node* root) { if (root nullptr)return; _inorder(root-_left); std::cout root-_key : root-_val ; _inorder(root-_right); } void destroy(node*root) { if (rootnullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; } node* _root nullptr; }; }