二叉树

2021-03-02 16:50:41 浏览:310

定义

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

作          者: 泮桥成像光电商城

出          处: https://www.ipanqiao.com/entry/346

版          权:本文版权归泮桥成像光电商城所有

免责声明:本文中使用的部分文字内容与图片来自于网络,如有侵权,请联系作者进行删除。

转          载:欢迎转载,但必须保留上述声明;必须在文章中给出原文链接;否则必究法律责任。

Copyright © 2019-2022 南京超维景生物科技有限公司 版权所有 www.ipanqiao.com苏ICP备20009590号-1
联系我们
立即做合同
微信客服
电话咨询

400-998-9826

17302548620

快速留言

泮桥成像光电商城专业人员会在24小时之内联系您

关闭 提交