大庆哈尔滨网站建设,微信开发者工具安装,中国互联网上网服务行业协会,深圳网站建设优化czzhwm文章目录 概念插入和删除非递归实现中的问题递归中的引用简化相关OJ复习直达 概念 由下面二叉搜索树的性质可以知道#xff0c;中序遍历它便可以得到一个升序序列#xff0c;查找效率高#xff0c;小于往左找#xff0c;大于往右走。最多查找高度次#xff0c;走到到空中序遍历它便可以得到一个升序序列查找效率高小于往左找大于往右走。最多查找高度次走到到空还没找到这个值不存在 插入和删除 替换法即找该删除结点中左子树中的最大结点或者右子树的最小结点进行替换再删除该结点这样可以保证二叉树的搜索性使该结点删除后还是二叉搜索树 非递归实现中的问题 下面这里删除13和14都是属于同一类型13的左孩子为nullptr则让13的父亲指向13的右孩子。删除14的时候14的左孩子不为nullptr则让14的父亲指向14的左孩子。这里很明显我们要记录删除结点的父结点同时还要判断删除结点是父节点的左孩子还是右孩子。若删除的孩子有左右孩子那么我们的先找个孩子替换它这个孩子必须是左子树的最大孩子或者右子树的最小孩子再像删除13和14一样删除这个结点 递归中的引用简化 在递归的时候传引用便可以解决判断删除结点是父结点的左孩子还是右孩子问题。我们不需要再记录父结点。通过下面这个案例来加深理解传引用赋值的话10的右指针直接指向14的左孩子13如果不传引用赋值的话那么10的右指针保存的地址不变还是14结点地址而14结点被delete掉了再次访问就会报错 相关OJ复习直达 1、二叉树的分层遍历2
2、二叉树搜索树转换成排序双向链表
3、根据二叉树的前序和中序遍历结果还原该二叉树
4、根据二叉树的中序和后序遍历结果还原该二叉树
5、二叉树的前序遍历非递归迭代实现
6、二叉树中序遍历 非递归迭代实现
7、二叉树的后序遍历 非递归迭代实现
