<p><strong><span style="color:#fe2c24;">有序二叉树</span></strong></p> 讯享网
左边节点值小于当前节点，右边节点值大于当前节点
插入
判断root是否为空
- root为空 root = node
- 如果root不为空
定义index游标，初始值==root
判断index和node节点值的大小
直到插入
所有二叉树的遍历
广度优先遍历
从上到下依次遍历，同一层从左到右遍历每个节点
借助队列实现：
- 根节点入队
- 只要队列不是空，就从队列中取数据
- 取出节点，并将该取出的节点的 左右孩子 入队
深度优先遍历
都是先左后右，看父
- 先序遍历
父 左 右 A B C
- 中序遍历
左 父 右 B A C
- 后序遍历
左 右 父 B C A
三个三个看
例：中序遍历：
删除
黑色表示要删除的节点；蓝色表示父节点；绿色表示孩子
删除叶子节点
1、找到要删除的节点 target
没有的话不删
2、找要删除节点的父节点 parent
- 如果没有父节点 root = null
- 如果有父节点
判断目标节点是父节点的左孩子还是右孩子
parent.left = null parent.right = null
删除只有一棵子树的节点
1、找到要删除的节点 target
没有的话不删
2、找要删除节点的父节点 parent
- 如果没有父节点 root = null
- 判断目标节点是左子树还是右子树
- 判断目标节点是父节点的左孩子还是右孩子
- 如果有父节点
- 判断目标节点是父节点的左孩子还是右孩子
讯享网
<ul><li>判断目标节点有左子树还是右子树</li></ul></li></ul></li></ul>
删除有两棵子树的节点（替换）
1、找到要删除的节点 target
没有的话不删
2、找目标节点左子树的最大值 或 右子树的最小值
3、目标节点左子树的最大值 或 右子树的最小值 ，替换target的值
4、删除目标节点左子树的最大值 或 右子树的最小值
- 判断目标节点是父节点的左孩子还是右孩子
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/197932.html