定义
二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构 。
图 1 一棵有9个节点且深度为3的二叉树，其根节点的值为2。
二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二分查找和二叉堆，并应用于高效率的搜索和排序。
二分查找应用举例：
1、我们把输入数组A进行升序排列，得到[0, 3, 4, 6, 7, 8, 11]；
2、令x = 2，数组中间的元素是6，2小于6，所以2只可能存在于6的左边，我们只需要在数组[0, 3, 4]中继续查找；
3、左边的数组中间的元素是3，2小于3，所以2只可能存在于3的左边，即数组[0]；由于数组[0]无法再分割，查找结束；
4、x需要跟我们最终找到的0，以及倒数第二步找到的3进行比较，发现2离3更近，所以查找结果为3。
这种查找方法就是二分查找，其算法复杂度为O(log2n)。
图 2 二分查找示例
参考文献
[1] https://zhuanlan.zhihu.com/p/45346117
