二叉查找树
2019-04-24 16:15:04 0 举报
二叉查找树的性质以及操作
作者其他创作
大纲/内容
3
3.5
6
1
5
操作:让该节点的父节点指向该节点的左孩子,然后删除该节点
8
7
0
4
1.5
2.然后按照情况2或3处理
如图:删除节点8
删除:
2
二叉查找树的性质: 1.若左子树不为空,则左子树的所有节点的值都小于根节点的值 2.若右子树不为空,则右子树的所有节点的值都大于根节点的值 3.根节点的左右子树也满足条件1和2
找到节点1右子树的最左节点替换掉节点1
1.8
9
如图:删除节点4
6.5
1.要删除的节点无左右孩子(可以当做情况2或3去处理,也可单独处理)
将节点3的右孩子指向节点3.5然后删除节点4
查找:例如查找2
将节点2的左孩子指向节点1.8然后删除节点1.5
操作:这种情况下直接删除节点即可如图:删除节点6
3.要删除的节点只有右孩子
操作:1.找到删除节点右子树的最左节点或左子树的最右节点替换掉要删除的节点
二叉查找树:
如图:删除节点1
插入:插入6.5
2.要删除的节点只有左孩子
将节点7的右孩子指向节点9然后删除节点8
直接删除节点6
4.要删除的节点既有左孩子,又有右孩子
0 条评论
下一页