二叉查找树算法
形成树型结构,在进行查找
public class BTreeSearch
{
public static int Max = 10;
public static int[] Data = { 15, 2, 13, 6, 17, 25, 37, 7, 3, 18 }; // 数据数组
public static int Counter = 1;
public static void main(String args[])
{
int i; // 循环计数变量
BNTreeArray BNTree = new BNTreeArray(); // 声明二叉树数组
BNTree.TreeData[0] = Data[0];
for (i = 1; i < Max; i++)
BNTree.Create(Data[i]); // 建立二叉查找树
int KeyValue = 25;
// 调用二叉查找法
if (BNTree.BinarySearch(KeyValue) > 0)
// 输出查找次数
System.out
.println("Search Time = " + BNTree.BinarySearch(KeyValue));
else
// 输出没有找到数据
System.out.println("No Found!!");
}
}
class BNTreeArray
{
public static int MaxSize = 20;
public static int[] TreeData = new int[MaxSize];
public static int[] RightNode = new int[MaxSize];
public static int[] LeftNode = new int[MaxSize];
public BNTreeArray()
{
int i; // 循环计数变量
for (i = 0; i < MaxSize; i++)
{
TreeData[i] = 0;
RightNode[i] = -1;
LeftNode[i] = -1;
}
}
// ----------------------------------------------------
// 建立二叉树
// ----------------------------------------------------
public void Create(int Data)
{
int i; // 循环计数变量
int Level = 0; // 树的阶层数
int Position = 0;
for (i = 0; TreeData[i] != 0; i++)
;
TreeData[i] = Data;
while (true) // 寻找节点位置
{
// 判断是左子树或是右子树
if (Data > TreeData[Level])
{
// 右树是否有下一阶层
if (RightNode[Level] != -1)
Level = RightNode[Level];
else
{
Position = -1; // 设定为右树
break;
}
}
else
{
// 左树是否有下一阶层
if (LeftNode[Level] != -1)
Level = LeftNode[Level];
else
{
Position = 1; // 设定为左树
break;
}
}
}
if (Position == 1) // 建立节点的左右连结
LeftNode[Level] = i; // 连结左子树
else
RightNode[Level] = i; // 连结右子树
}
// ---------------------------------------------------------
// 二叉查找法
// ---------------------------------------------------------
public static int BinarySearch(int KeyValue)
{
int Pointer; // 现在的节点位置
int Counter; // 查找次数
Pointer = 0;
Counter = 0;
while (Pointer != -1)
{
Counter++;
// 找到了欲寻找之节点
if (TreeData[Pointer] == KeyValue)
return Counter; // 传回查找次数
else if (TreeData[Pointer] > KeyValue)
Pointer = LeftNode[Pointer]; // 往左子树找
else
Pointer = RightNode[Pointer];// 往右子树找
}
return 0; // 该节点不在此二叉树中
}
}
总结下:
一 线性查找
又称顺序查找,是从数组的第一个元素开始查找,直到找到待查找元素的位置,直到查找到结果。
最佳的状况时间是1 ,就是第一个就是待查找的远射,最差的查找状况是O(n),就是最后一个是待查找的元素。
二 折半查找
折半查找是将待查找的数组元素不断的分为两部分,每次淘汰二分之一,但是有个大前提是,元素必须是有序的,如果是无序的则要先进行排序操作,这种查找的方法,类似于找英文字典的Java,我们可以一下子找到字母J开头的,再仔细找。
最佳的状况时间是1,就是第一次分开就查找到了,最差的查找状态是O(n),便是待查找的数据出现在最后一次。
三 费氏查找
费氏查找主要是根据费氏数列1 1 2 3 5 8 13 ...... 来确定范围,然后再进行查找
四 插补查找
插补查找是一种类似折半查找的查找方法,插补查找是以比例的概念,求出待查找数据的可能位置,然后进行比较,如果该值比待查找的小,表示待查找的值可能出现在该值之前的范围,就这样一直缩小范围来确定最终的目标。
五 二叉查找树
二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。
这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。
以上就是对查找算法的小小总结,在以后的应用中我们应该根据具体的问题具体分析,找到解决问题的最优解决方案。
原文网址:
http://blog.csdn.net/myjava_024/archive/2008/11/20/3342539.aspx
分享到:
相关推荐
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
DataStructuresAlgorithms 数据结构和算法
凸包问题(包含蛮力算法和快速凸包算法两种解法)+最优二叉查找树,并且都利用javafx生成可视化界面,开箱即用,代码含注释,原理通俗易懂。
熟练运用顺序查找、二分查找和二叉搜索树等查找算法 二、实验原理 对顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。于任意一个序列以及一个给定的元素,将给定元素与序列中元素依次比较,直到...
:thinking_face: 算法 基于Java 8实现的代码片段集合,可以在之上的同步理解这些...与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分查找-BinarySearch 广度优先搜索 深度优先搜索
word源码java MAPLE NOTES 路过的小伙伴们,大家好,我是笑小枫,专注于JAVA开发 JAVA日常笔记 日常开发常用命令 Java文档: SpringBoot文档: ...查找算法 二分查找: 排序算法 冒泡排序: 选择排序: 插入排序:
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分...
java 算法:包括数组,哈希表,队列,栈,链表(双端,单向,双向),二叉树(普通二叉树,哈夫曼树,二叉查找树,平衡二叉树,二叉线索树),图这些数据结构的实现以及多种排序算法和其他一些算法的实现(递归,二...
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现...第26章 二叉查找树(层次结构) 第27单 图及其应用 第28章 加权图及其应用 第29章 多线程
视频详细讲解,需要的小... 二叉查找树;第四章: 堆; 优先队列; 2-3查找树; 红黑树;第五章: B-树; B+树; 并查集; 无向图;第六章: 有向图; 拓扑排序; 加权无向图; 最小生成树; 加权有向图; 最短路径;
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
4.3 查找树ADT——二叉查找树 4.3.1 contains方法 4.3.2 findMin方法和findMax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 AVL树 4.4.1 单旋转 4.4.2 双旋转 4.5 伸展树 4.5.1 一个简单的想法...
初级java笔试题算法 Coursera - 普林斯顿大学课程 教学大纲 说明。 基本数据类型、算法和数据结构的介绍。 我们的重点是 Java 实现的应用程序和科学性能分析。 Part I 重点介绍基本data structures 、 sorting和...
C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
3.3.2 红黑二叉查找树 3.3.3 实现 3.3.4 删除操作 3.3.5 红黑树的性质 3.4 散列表 3.4.1 散列函数 3.4.2 基于拉链法的散列表 3.4.3 基于线性探测法的散列表 3.4.4 调整数组大小 3.4.5 内存使用 3.5 应用 ...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...