当前位置：首页 > news >正文

二叉树的进阶

news 2025/4/24 12:46:05

前言：

关于二叉树的基础知识，小生这里就不在一一一赘述了，对前面二叉树的基础知识有遗忘的铁子

们，可以康康前期咱的博客。

链接在此： 数据结构之二叉树的精讲

//1）先对删除节点的孩子情况进行判断便于后期父节点孩子与删除节点的孩子进行链接if (cur->_left == nullptr){//2）必须先判断删除的节点是否为根节点：只有一个节点的二叉搜索树同时也是一个叶节点if (cur == _root){_root = _root->_right;delete cur;return true;}else{//3）再进行判断删除节点是左孩子还是右孩子if (cur == parent->_left){parent->_left = cur->_right;delete cur;return true;}else{parent->_right = cur->_right;delete cur;return true;}}}else if (cur->_right == nullptr){//这个整体的框架和上面删除一样//是否删除根节点if (cur == _root){_root = _root->_left;delete _root;return true;}else{// 删除的节点是左孩子还是右孩子if (parent->_left == cur){parent->_left = cur->_left;delete cur;return true;}else{parent->_right = cur->_left;delete cur;return true;}}}

3）删除有左右孩子的节点

对应的代码：

//1)先找到右子树的最小节点：注意最小节点拷贝一定就是在左面：也可能最小节点是删除节点的右孩子TreeNode* subLeft = cur->_right;while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}//找到了最小节点但是可能存在循环不进入的情况，所有parent可能为空，在初始化的时候parent= cur即可即可解决此问题//2)对_key  进行交换,目的转化为对最小节点的删除swap(cur->_key, subLeft->_key);//swap(key, subLeft->_key);//err// 3)判断subLeft是左孩子还是右孩子if (subLeft == parent->_left){parent->_left = subLeft->_right;delete subLeft;return true;}else{//parent->_right = subLeft->_left;//err这样写，当subLeft是叶节点的时候OK，但是当这是一个右叉树的时候，只能指向subLeft 的右孩子parent->_right = subLeft->_right;delete subLeft;return true;}}

对于容器一般进行的操作无非就是常见的“增删查改”。但是对于二叉搜索树进行修改操作后不一定

能保证修改之后还是一棵完整的二叉搜索树。

二叉树的常用函数：

拷贝构造函数：使用先序遍历进行创建

对于拷贝构造函数的递归调用见下：

这里有个小问题：对于参数为什么不能使用引用传参，也就是 TreeNode* & root

本质问题是：权限放大的问题

此时实参被const 进行修饰了，当在调用Copy(TreeNode* & root) 的时候，编译器会生成一个临时

对象，这个临时对象无法赋值给形参，因为权限被放大了。

注意：在传参的时候参数不是直接就传给形参了，而是编译器借助另一个临时变量，把实参赋值给

一个临时变量，再通过临时变量赋值给给形参，但是这样的效率比较慢。所以C++提出使用引用这

个概念，来解决此问题。

对于引用相关知识点，小生在这里就不在多多叨叨了，链接在此：引用相关介绍

赋值重载函数：

析构函数：

使用后续遍历进行销毁

接下来“硬菜”来了，使用递归编写对节点的删除代码：

 bool _EraseR(TreeNode* root, const k& key){//1:先对删除 的节点进行查找if (root->_key > key)_Erase(root->_left, key);else if (root->_key < key)_Erase(root->_right, key);else{//准备删除//2）判断删除节点左和右孩子是否为空if (root->_left == nullptr){//关键就是如何取到删除节点的父节点//参数：传引用TreeNode* del = root;root = root->_right;delete del;return true;}else if (root->_right == nullptr){TreeNode* del = root;root = root->_left;delete del;return true;}else{//删除节点的左右孩子都不为空//1:找右子树最小节点TreeNode* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}swap(root->_key, subLeft->_key);//转化为对subLeft所在的子树进行删除subLeft这个节点_Erase(root, key);return true;}}return false;}