二叉搜索树

二叉搜索树概念

  二叉搜索树又称二叉排序树或二叉查找树，是二叉树的一种，他具备以下三个特点。

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。

  简单来说就是这个二叉树的所有节点都满足：左孩子<父节点<右孩子。

二叉搜索树操作

二叉搜索树的查找

  二叉搜索树的查找有点类似二分查找，比根节点小就去左子树，比根节点大就去右子树。最多可以查找高度次，走到空还没找到就说明这个值不存在。

二叉搜索树的插入

  先是按照查找的方式来走，遇到空就把这个节点插入，这样就完成了二叉搜索树的插入。

二叉搜索树的删除

  删除二叉搜索树中的节点需要根据不同情况来出来。

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。