有序数组的优点：
在有序数组中查找数据可以用二分查找法，用这个方法在查找时效率很高，所需时间是0（logN），
然而在插入或者删除数据时，需要平均移动N/2项数据，如果需要做很多的插入删除操作，就不应该用有序数组。
链表的优点：
链表在插入或者删除时，操作很快，只需要修改对前一个节点的引用，修改后一个节点的引用，就能完成，所需时间复杂度为O（1），
但是在查找数据是，需要链表头开始，平局需要移动N/2个数据，如果需要做很多查找操作，就不应该用到链表。
树是一种能将有序数组和链表优点结合使用的数据结构，这里首先研究二叉树，每个节点最多只有两个子节点，这里假设对二叉树的概念都很清楚。
查找二叉树节点。根据二叉树的特点，左子节点值总比父节点的小，右子节点的值总比父节点大。
因此，当查找值小于节点值，应该向左子树查找；当查找值大于节点值，应该向右子树查找。
图解：假设需要查找57，则查找路线如下图。
查找代码：
/** * 查找节点 * * @param key 输入key值 * @return 返回节点值 */ public Node find(int key) { // 当前节点，相当于一个指针，引用会随着查找变化 Node current = root; // 遍历查询节点 // 查找方法：根据二叉树的特点，左子节点值总是比父节点值小，右子节点值总比父节点值大 while (current.iData != key) { // 比较当前节点值， if (key < current.iData) { // 如果值小于key，则将当前节点current引用变化为左子节点，此时不用判断引用是否为null current = current.leftChild; } else { // 如果值大于key，则将当前节点current引用变化为右子节点，此时不用判断引用是否为null current = current.rightChild; } // 如果当前节点为空，则表示无法找到key对应的节点 if (current == null) { return null; } } return current; }
1.这个过程用变量current来表示当前节点（相当于指针），参照key值为要查找的值，因为查找使用root开始的，而且也只知道root的值，所以一开始把root的引用赋值给current。
2.查找过程中，按照二叉树的特点，通过key < current.iData判断是找左子节点，还是右子节点。
3.如果找到，返回current值；否则，返回null。
可以这样理解，方便记忆：
经过while循环后，每一次循环结束后，current值就变为key所在子树的根（其实是引用变化），看成是一颗新的树。
树的效率：
因为只有在每一层的某一个节点比较（可能是左子节点，也可能是右子节点），所有比较的次数取决于二叉树的层数，所以查找的时间复杂度为O（logN）.
原文：http://www.cnblogs.com/winlrou/p/3535227.html