怎么做服务器网站,pageadmin做的网站的域名必须要备案吗,昆明中国建设银行网站,小程序代理好做吗目录
1. find 的递归实现
2. insert 的递归实现
3. erase 的递归实现
3.1. 被删除的节点右孩子为空
3.2. 被删除的节点左孩子为空
3.3. 被删除的节点左右孩子都不为空
4. 析构函数的实现
5. copy constructor的实现
6. 赋值运算符重载
7. 搜索二叉树的完整实现 1. fi…目录
1. find 的递归实现
2. insert 的递归实现
3. erase 的递归实现
3.1. 被删除的节点右孩子为空
3.2. 被删除的节点左孩子为空
3.3. 被删除的节点左右孩子都不为空
4. 析构函数的实现
5. copy constructor的实现
6. 赋值运算符重载
7. 搜索二叉树的完整实现 1. find 的递归实现 find的递归实现较为简单思路是根据当前节点的 key 与传入的 key 作比较 如果前者大于后者那么当前节点往左子树走如果前者小于后者那么当前节点往右子树走如果两者相等返回true走到空返回false。 代码实现 // 对外提供的
bool find_recursion(const T key)
{return _find_recursion(_root, key);
}
// 类中私有的
bool _find_recursion(Node* root, const T key)
{if (root nullptr)return false;else{if (root-_key key)return _find_recursion(root-_right, key);else if (root-_key key)return _find_recursion(root-_left, key);elsereturn true;}
}
2. insert 的递归实现 insert分为两个过程 第一个过程找到合适位置第二个过程构建新节点并完成连接关系。 假如现在我们已经得到了合适的插入位置那么如何连接呢 例如如下图所示我们要插入13这个数据现在的关键问题是如何将15和13这两个节点连接起来呢 具体如下 第一种方法调用函数时将父亲节点即这里的15也传进来。找到合适位置创建节点并连接。 但是我们在这里提出一个较好玩的玩法利用引用传参如下所示 // 对外提供的
bool insert_recursion(const T key)
{ return _insert_recursion(_root, key);
}
// 类中私有的
bool _insert_recursion(Node* root, const T key)
{if (root nullptr){// 走到空, 说明找到了目标位置, 需要构建新节点, 并完成连接关系// 在这里, 我们用上图解释:// root就是15这个节点的左孩子的引用即root就是15的左孩子// 给root new了一个node(key),等价于插入了这个节点,并连接了起来.root new Node(key);return true;}else{if (root-_key key)return _insert_recursion(root-_right, key);else if (root-_key key)return _insert_recursion(root-_left, key);elsereturn false;}
}
3. erase 的递归实现 对于erase的递归实现其实也可以分为两个过程 第一个过程找到这个要删除的特殊节点第二个过程可以分为三种情况(左孩子为空、右孩子为空、左右孩子都不为空)根据不同情况进行删除。 假设我们现在已经得到了要删除节点的位置该如何删除呢 3.1. 被删除的节点右孩子为空 如图所示我们要删除6号节点(其右孩子为空)该如何删除 由于 root 是4的右孩子的引用且 root 的右孩子为空那么root root-_left就可以将4的右孩子由6变更为5我们在删除6即可因此我们需要提前保存6节点当指向变更之后delete 6。 3.2. 被删除的节点左孩子为空 如图所示我们要删除15号节点(其左孩子为空)该如何删除 由于 root 是8的右孩子的引用且 root 没有左孩子那么我们此时只需要更改 root 即可让 root 到它的右孩子 (root root-_right)等价于将8连接了19当然我们也需要提前将 root 节点进行保存更改指向后在释放 root 节点即可。 3.3. 被删除的节点左右孩子都不为空 较为复杂的就是第三种情况了由于此时被删除节点有两个孩子因此无法像上面两种情况进行处理。此时我们还是要利用循环实现的思路 (1)从被删除的节点开始先找到左子树的最大节点or右子树的最小节点(我在这里称之为合适节点)(2)交换这个合适结点和被删除节点的key(3)将删除原节点转化为删除我们后找的这个合适节点。 在这里我们用实例说明如下图所示如果我要删除下图中的4该如何删除 我在这里实现的合适节点是 左子树的最大(右)节点 相信前两个过程是没有困难的最后一步可能不好实现但是当我们经过了前两个过程我们发现被删除节点变成了我们找到的合适节点而且这个合适节点很有特征如果它是左子树的最大值那么它一定不会有右子树反之如果他是右子树的最小节点那么它一定不会有左子树。因此我们可以在递归一次如果合适节点是左子树的最大节点那么我们递归树的左子树即可反之如果是右子树的最小节点那么我们递归树的右子树即可。 代码如下 // 对外提供的
bool erase_recursion(const T key)
{return _erase_recursion(_root, key);
}
// 类中私有的
bool _erase_recursion(Node* root, const T key)
{if (!root)return false;else{// 如果当前节点的key 目标key那么递归它的左子树即可if (root-_key key)return _erase_recursion(root-_left, key);// 如果当前节点的key 目标key那么递归它的右子树即可else if (root-_key key)return _erase_recursion(root-_right, key);// 如果找到了,进行删除else{// 此时的root就是要删除的节点Node* del root;// a. 左子树为空if (root-_left nullptr)root root-_right;// b. 右子树为空else if (root-_right nullptr)root root-_left;// c. 左右子树都不为空else{// 左子树的最右节点Node* left_max root-_left;while (left_max-_right)left_max left_max-_right;// 交换合适节点和被删除节点的keystd::swap(left_max-_key, root-_key);// 在这里递归左子树即可return _erase_recursion(root-_left, key);}delete del;del nullptr;return true;}}
}
4. 析构函数的实现 析构函数的实现我们依据的是后序的思想(LRN)先析构左子树、然后是右子树、最后才是根。这种实现的原因是是少了许多的记录信息例如在这里我们就不用记录下一个节点。因为我们释放的就是当前的叶子节点。 具体实现如下 ~BinarySearchTree()
{_BSTDestroy(_root);
}
// 注意我们这里传递的是根的引用
void _BSTDestroy(Node* root)
{if (root nullptr)return;else{// 依据后序的思想_BSTDestroy(root-_left);_BSTDestroy(root-_right);delete root;root nullptr;}
}
5. copy constructor的实现 老生常谈的问题如果我们没有显示实现拷贝构造函数那么编译器默认生成的拷贝构造会对内置类型按照字节序的方式进行拷贝对自定义类型成员属性会去调用它的拷贝构造函数。而字节序的方式进行拷贝会带来两个问题 其一其中一个对象的修改会影响另一个对象其二同一空间会被析构两次进程crash。 因此我们在这里必须要实现深拷贝那如何实现呢我们可以借助前序的思想(NLR)。从根节点开始进行构造节点然后递归构造它的左子树和右子树。注意构造的时候需要它们的连接关系。 代码如下 BinarySearchTree(const BinarySearchTreeT copy)
{_root _creat_new_root(copy._root);
}
Node* _creat_new_root(Node* root)
{// 如果遇到空了,就不用构造了if (root nullptr)return nullptr;else{// 根据前序的思想(NLR),依次构造它的根、左子树、右子树 // 同时将它们连接起来Node* new_root new Node(root-_key);new_root-_left _creat_new_root(root-_left);new_root-_right _creat_new_root(root-_right);return new_root;}
}
6. 赋值运算符重载 赋值运算符重载就比较简单了因为我们已经实现了copy constructor在这里利用传值传参会进行拷贝构造的特性实现我们的赋值 代码如下 // 传值传参会进行拷贝构造
BinarySearchTreeT operator(BinarySearchTreeT copy)
{std::swap(_root, copy._root);return *this;
}
7. 搜索二叉树的完整实现 代码如下 #ifndef _BINARY_SEARCH_TREE_HPP_
#define _BINARY_SEARCH_TREE_HPP_#include iostreamnamespace Xq
{templateclass Tstruct BinarySearchTreeNode{BinarySearchTreeNodeT* _left;BinarySearchTreeNodeT* _right;T _key;BinarySearchTreeNode(const T key) :_key(key), _left(nullptr), _right(nullptr) {}};templateclass Tclass BinarySearchTree{private:typedef BinarySearchTreeNodeT Node;public:BinarySearchTree(Node* root nullptr) :_root(root) {}bool insert(const T key){// 1. 如果是空树,直接对_root赋值即可,插入成功并返回trueif (_root nullptr){_root new Node(key);return true;}else{// step 1: 先找目标位置Node* cur _root;// 为了更好的连接新节点, 因此记录父节点Node* parent nullptr;while (cur){// 如果当前节点的Key大于目标Key// 当前节点应该向左子树走if (cur-_key key){parent cur;cur cur-_left;}// 如果当前节点的Key小于目标Key// 当前节点应该向右子树走else if (cur-_key key){parent cur;cur cur-_right;}else{// 找到了相同的 key, 在这里不插入return false;}}// cur 走到了空, 即 cur 就是合适的位置cur new Node(key);// 我们需要判断cur是parent的左节点还是右节点// 如果key小于parent的key,那么插入左节点if (key parent-_key)parent-_left cur;// 反之连接到右节点elseparent-_right cur;return true;}}bool find(const T key){// 1. 从根节点开始Node* cur _root;while (cur){// 2. 如果当前关键字大于目标关键字,那么向左子树走if (cur-_key key)cur cur-_left;// 3. 如果小于目标关键字,那么向右子树走else if (cur-_key key)cur cur-_right;// 4. 相等就返回trueelsereturn true;}// 5. 循环结束,说明没找到, 返回falsereturn false;}bool erase(const T key){// 先找要删除的节点Node* del _root;Node* del_parent nullptr;while (del){if (del-_key key){del_parent del;del del-_right;}else if (del-_key key){del_parent del;del del-_left;}else{// 锁定了要删除的节点// 分三种情况:// case 1: 左子树为空if (del-_left nullptr){// 如果要删除的节点是根if (del _root){Node* newroot del-_right;delete _root;_root newroot;}else{// 托孤法删除if (del_parent-_left del)del_parent-_left del-_right;elsedel_parent-_right del-_right;delete del;del nullptr;}}// case 2: 右子树为空else if (del-_right nullptr){if (_root del){Node* newroot del-_left;delete _root;_root newroot;}else{if (del_parent-_left del)del_parent-_left del-_left;elsedel_parent-_right del-_left;delete del;del nullptr;}}// case 3: 左右子树都不为空else{// 从被删除节点开始, 找右子树的最小(左)节点 || 找左子树的最大(右)节点if (del-_right)_erase_right_min_node(del);else_erase_left_max_node(del);}return true;}}return false;}bool find_recursion(const T key){return _find_recursion(_root, key);}bool insert_recursion(const T key){return _insert_recursion(_root, key);}bool erase_recursion(const T key){return _erase_recursion(_root, key);}~BinarySearchTree(){_BSTDestroy(_root);}BinarySearchTree(const BinarySearchTreeT copy){_root _creat_new_root(copy._root);}// 传值传参会进行拷贝构造BinarySearchTreeT operator(BinarySearchTreeT copy){std::swap(_root, copy._root);return *this;}void InOrder(){_InOrder(_root);std::cout std::endl;}private:void _InOrder(Node* root){if (root){_InOrder(root-_left);std::cout root-_key ;_InOrder(root-_right);}}bool _find_recursion(Node* root, const T key){if (root nullptr)return false;else{if (root-_key key)return _find_recursion(root-_right, key);else if (root-_key key)_find_recursion(root-_left, key);elsereturn true;}}bool _insert_recursion(Node* root, const T key){if (root nullptr){root new Node(key);return true;}else{if (root-_key key)return _insert_recursion(root-_right, key);else if (root-_key key)return _insert_recursion(root-_left, key);elsereturn false;}}void _erase_right_min_node(Node* del){// 从被删除结点开始, 找右子树的最小(左)节点Node* right_min del-_right;// 并记录这个节点的父亲节点, 让其从del开始Node* right_min_parent del;while (right_min-_left){right_min_parent right_min;right_min right_min-_left;}// 交换这个节点和要删除节点的 keystd::swap(del-_key, right_min-_key);// 将删除 del 转化为删除 right_min (托孤法删除)if (right_min_parent-_left right_min)right_min_parent-_left right_min-_right;elseright_min_parent-_right right_min-_right;delete right_min;right_min nullptr;}void _erase_left_max_node(Node* del){// 从被删除节点开始, 找左子树的最大(右)节点Node* left_max del-_left;// 并记录这个节点的父亲节点, 让其从del开始Node* left_max_parent del;while (left_max-_right){left_max_parent left_max;left_max left_max-_right;}// 交换这个节点和要删除节点的 keystd::swap(del-_key, left_max-_key);// 将删除 del 转化为删除 left_max (托孤法删除)if (left_max_parent-_left left_max)left_max_parent-_left left_max-_left;elseleft_max_parent-_right left_max-_left;delete left_max;left_max nullptr;}bool _erase_recursion(Node* root, const T key){if (!root)return false;else{// 如果当前节点的key 目标key那么递归它的左子树即可if (root-_key key)return _erase_recursion(root-_left, key);// 如果当前节点的key 目标key那么递归它的右子树即可else if (root-_key key)return _erase_recursion(root-_right, key);// 如果找到了,进行删除else{// 此时的root就是要删除的节点Node* del root;// a. 左子树为空if (root-_left nullptr)root root-_right;// b. 右子树为空else if (root-_right nullptr)root root-_left;// c. 左右子树都不为空else{// 左子树的最右节点Node* left_max root-_left;while (left_max-_right)left_max left_max-_right;// 交换合适节点和被删除节点的keystd::swap(left_max-_key, root-_key);// 在这里递归左子树即可return _erase_recursion(root-_left, key);}delete del;del nullptr;return true;}}}Node* _creat_new_root(Node* root){// 如果遇到空了,就不用构造了if (root nullptr)return nullptr;else{// 根据前序的思想(NLR),依次构造它的根、左子树、右子树 // 同时将它们连接起来Node* new_root new Node(root-_key);new_root-_left _creat_new_root(root-_left);new_root-_right _creat_new_root(root-_right);return new_root;}}// 注意我们这里传递的是根的引用void _BSTDestroy(Node* root){if (root nullptr)return;else{// 依据后序的思想_BSTDestroy(root-_left);_BSTDestroy(root-_right);delete root;root nullptr;}}private:Node* _root;};
}#endif 二叉树进阶 --- 中结束。
