二叉查找树

定义

1. 某节点的左子树节点值仅包含小于该节点值
2. 某节点的右子树节点值仅包含大于该节点值
3. 对于根节点，最多有俩个直接相邻的子节点

图形

优点

二叉树时间复杂度为logn，因为平均情况下把一个n变为1的时候，满足公式n*(1/2)^k = 1，也就是需要执行的操作步数k为logn。

缺点

如果不进行调整，二叉查找树会出现退化的情况。

怎么统计二叉树中每个节点有几个子节点？

父节点的子节点个数 等于 左孩子节点的个数+有孩子节点的个数。用递归实现时，当遍历完左子树和右子树时，如果此时左孩子节点不为空，则左子树的个数为左孩子节点的个数+1，否则为0。右子树同理。

怎么从二叉搜索树中快速查找出第k小的值？

题目分析

我们知道二叉搜索树的特点，父节点大于左孩子节点，父节点大于有孩子节点。对于每个父节点，最多有俩个孩子节点。 根据这个特性，我们知道最小节点就是最左边的节点，最大节点就是最右边的节点。那么第二小和第二大节点呢？第二小，就是这个最小节点的直接相邻父节点，或者是这个最小节点的直接相邻的右孩子节点，第二大节点同理。

由上面分析可见，我们稍加分析就可以知道，这求第k小的值 可以在遍历二叉搜索树的时候得到。当一个父节点没有左子树或者遍历完左子树的时候，那么它就是最小的。

实战题目

二叉搜索树的第k个节点