定义
二叉树(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