定义
可以为空,如果不为空的话,需要满足以下条件:
- 左子树所有键值小于其根节点的键值
- 右子树所有键值大于其根节点的键值
- 左右都是二叉查找树
操作函数
- 查找函数
与节点作比较,小于节点就到左子树,大于节点就到右子树查找
两种实现方法:
一种是递归实现,代码很简洁,效率不高,属于伪递归
一种是循环实现,从编译的角度,所有的伪递归都可以用循环实现 - 查找最大元素和最小元素
最大元素,一定是最右边;最小元素,一定是最左面 - 二叉树的插入
关键是找到元素的插入位置,而且在插入的时候,要往哪插?这里需要记录上一个节点 - 二叉树的删除
三种情况:- 删除叶节点:直接删除,将父节点相关的指针设为null
- 删除节点只有一个孩子:将父节点的指针指向要删除节点的孩子节点
- 删除的节点左右都有孩子:用左子树的最大元素或右子树的最小元素替代被删除节点
网友评论