数据结构 |
您所在的位置：网站首页 › 二叉排序树建立及查找 › 数据结构 |
数据结构
|
目录 二叉查找树 二叉查找树的实现 1、查询 2、新增 3、删除 支持重复数据的二叉查找树 二叉查找树的性能分析 二叉查找树二叉查找树又称二叉搜索树，也被称为二叉排序树 问题一：什么样的树才是二叉查找树？ 在树中的任意节点，其左子树中的每一个节点均小于该节点值，其右子树中的值均大于该节点的值。 如果使用中序遍历，遍历二叉查找树，可以输出一个有序的数据序列，时间复杂度为O(n),非常高效。 二叉查找树的实现 1、查询 先取根节点与要查询的数据进行比较，如果等于根节点，那就返回。如果大于根节点，那就在右子树种递归查找，如果小于根节点，那就在左子树种查找 代码示例： public class BinaryTree { private Node tree; //查找操作 public boolean find(int num){ Node p=tree; while (p!=null){ if(p.data==num) return true; if(p.data>num){ p=p.leftChild; //递归查找左子树 } else if(p.data p.data){ p=p.rightChild; }else{ p=p.leftChild; } } if(p==null) return false; //没有找到 //需要删除的节点有两个子节点的情况 if(p.leftChild!=null && p.rightChild!=null){ //查找右子树中的最小数据的节点 Node minp=p.rightChild; Node minFather=p; while (minp.leftChild!=null){ minFather=minp; minp=minp.leftChild; } p.data=minp.data; //将右子树中最小节点minp的数值替换要删除节点p中 p=minp; //下面就就变成需要删除右子树中的最小节点minP father=minFather; } //需要删除的节点只有一个子节点或没有节点的情况 Node child; // 要删除节点p的子节点 if(p.leftChild!=null){ child=p.leftChild; }else if(p.rightChild!=null){ child=p.rightChild; }else { child=null; } if(father == null) tree=child; //如果父节点为null，删除根节点 else if(father.leftChild ==p) father.leftChild=child; else father.rightChild=child; return true; }除了查询、插入、删除操作之外，还有快速查询最大节点和最小节点，前驱节点和后继节点等操作，这里就不一一实现了。 支持重复数据的二叉查找树 在实际的开发过程中，二叉查找树存储的是一个包含很多字段的对象，我们利用对象的某个字段作为键值(key)来构建二叉查找树，把对象中的其他字段叫做卫星数据。
上面介绍的二叉查找树，针对的是键值都不相同的情况。如果存储的两个对象键值相同，那又该如何处理呢？？？ 方案一：二叉查找树中的每一个节点会存储多个数据，因此我们可以通过链表和支持动态扩容的数组等数据结构，把相同的数据存储在同一个节点上 方案二：每个节点仍然只存储一个数据，插入过程中，如果碰到相同的值，我们把插入的数据放到这个节点的右子树上，也就是说把这个值当作大于这个节点的值来处理。如下图。
查找操作的时候，遇到相同的节点，我们并不停止查找操作。而是继续在右子树中查找，直到遇到叶子节点，才停止。这样我们就可以把键值等于要查找值得所有节点都找出来了。 删除操作，我们先查找到所有需要删除得节点，然后按照前面所有讲的方式进行删除。 二叉查找树的性能分析 二叉查找树的形态各式各样，如下图，同一组数据，构造了三个不同的二叉树。不同的形态，其查询、新增、删除操作的时间复杂度也不一样。
由上图可以看出，二叉查找树的时间复杂度跟树的高度(height)成正比，也就是O(height)。 当一颗二叉树退化为链表的时候，查询，新增，删除的时间复杂度就变成了O(n)。 如果二叉查找树是一颗完全二叉树，就可以推导出树的层数(L)和节点数n之间的关系 如下： n >= 1+2+4+8+...+ n |
【本文地址】
今日新闻 |
推荐新闻 |