算法基础6：二叉树查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法基础6：二叉树查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1595字，纯文字阅读大概需要3分钟。

内容图文

算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第6篇《二叉树查找》，非常赞！希望对大家有帮助，大家会喜欢！

前面系列文章：

归并排序

#算法基础#选择和插入排序

由快速排序到分治思想

算法基础：优先队列

二分查找

1、二叉树

在链接二叉树查找之前我们要了解一下二叉树是个什么玩意。

二叉树指的数一颗最多只有两个两个子树的数据树型数据结构。其两个子树分别称为左子树和右子树，一个在根节点的左边，一个在根节点的右边 这就是一颗二叉树。下面这些都是二叉树。

2、二叉查找树

在了解了二叉树的前提下，我们可以聊聊二叉查找树。二叉查找树是一个特殊的二叉树。他同样具有最多只有两个子树的特性。但是他的特别点在于其左子树大于根节点。其右子树小于根节点。

3、二叉查找树实现查找

因为二叉查找树的特殊特性使用它可以很方便的对队列的的数据进行查找和插入和删除。

器查找实现原理如下：他先找到根节点和根节点对比大小之后，如果大于根节点则去左节点去查找，如果还是大于左节点的话，则继续找左节点的左节点。如果小于左节点的话，则找做节点的右节点，若是查找的节点为空了。则表示不存在这个值。 若是等于了，就表示找到对应的值。同理如果小于根节点则去右节点查找和左节点一样。

具体代码如下：

 public Value get(Key key){

  return get(root, key);

  }

  private Value get(Node x,Key key){

  if(x==null) returnnull;

  intcmp=key.compareTo(x.key);

  if(cmp<0) return get(x.left,key);

  elseif(cmp>0) return get(x.right,key);

  elsereturnx.value;

  }

特性：查找速度 1.39lgN 插入速度 1.39lgN

优缺点：

优点：和二分查找对比起来，插入速度更快二分查找插入的速度是N/2 插入速度是1.39lgN

缺点：查找慢和二分查找对比起来二分查找的查找速度为lgN 所以比二分查找慢39%

应用：

我们之后会说的二三树，红黑树，B-树都是基于二叉查找树扩展实现的，理解了二叉树，理解剩下的这些相对容易些。

内容总结

以上是互联网集市为您收集整理的算法基础6：二叉树查找全部内容，希望文章能够帮你解决算法基础6：二叉树查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---