有序二叉树
左边节点值小于当前节点,右边节点值大于当前节点
插入
判断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
- 判断目标节点是左子树还是右子树
- 判断目标节点是父节点的左孩子还是右孩子
- 如果有父节点
- 判断目标节点是父节点的左孩子还是右孩子
- 判断目标节点有左子树还是右子树
- 判断目标节点是父节点的左孩子还是右孩子
删除有两棵子树的节点(替换)
1、找到要删除的节点 target
没有的话不删
2、找目标节点左子树的最大值 或 右子树的最小值
3、目标节点左子树的最大值 或 右子树的最小值 ,替换target的值
4、删除目标节点左子树的最大值 或 右子树的最小值
标签:左子,遍历,删除,右子,改查,增删,操作,root,节点 From: https://blog.csdn.net/qq_73993301/article/details/143377288