Java里面没有直接提供树的实现，但是它很容易通过下面的方式来实现。只需要创建一个Node对象，里面包含一个指向叶子节点的ArrayList。

 

package bigo;
import java.util.ArrayList;
import java.util.List;
public class Node {
private String name;
private List<node> children = new ArrayList<node>( );
private Node parent;
public Node getParent( ) {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(String name) {
this.name = name;
}
public void addChild(Node child) {
children.add(child);
}
public void removeChild(Node child) {
children.remove(child);
}
public String toString( ) {
return name;
}
}

 

　　只要数据元素的关系可以表示成节点和边的网状结构的话，可以用图来表示。树是一种特殊的图，它的所有节点都只能有一个父节点。和树不同的是，图的形状是由实际问题或者问题的抽象来决定的。例如，图中节点（或者顶点）可以表示不同的城市，而图的边则可以表示两个城市之间的航线。

　　在Java里构造一个图，你需要解决数据通过什么方式保存和访问的问题。在图里面也会用到上面提到的数据结构。Java的API里没有提供图的实现。不过有很多第三方库里提供了，例如JUNG，JGraphT，以及JDSL（不过好像不支持泛型）。《Core Java Career Essential》一书包含了用Java实现的可用示例。
　　Q:你对大O这个符号有什么了解呢，你是否可以根据不同的数据结构举出一些列子来？
　　A：大O符号可以表示一个算法的效率，也可以用来描述当数据元素增加时，坏情况下的算法的性能。大O符号也可以用来衡量的性能，例如内存消耗量。有时候你可能会为了减少内存使用量而选择一个比较慢的算法。大O符号可以表示在大量数据的情况下程序的性能。不过，对于程序在大量数据量下的性能的测量，比较实际的方式是行用较大的数据集来进行性能基准测试，这样可以把一些在大O复杂度分析里没有考虑到的情况包含进去，例如在虚拟内存使用比较多的时候系统会发生换页的情况。虽然基准测试比大O符号表示的结果更加实际，但是它不适用于设计阶段，所以在这个这时候大O复杂度分析是合适的选择。
　　各种数据结构在搜索，插入和删除算法上的性能都可以用下面方式表示：常量复杂度O(1)，线性复杂度O(n)，对数复杂度O(log n)，指数复杂度O(c^n)，多项式复杂度O(n^c)，平方复杂度O(n^2)以及阶乘复杂度O(n!)，这里面的n都指的是数据结构里的元素的数量。性能和内存占用是可以相互权衡的。下面是一些示例。
　　示例1：在HashMap里查找一个元素的的时间复杂度是常量的，也即是O(1)。这是因为查找元素使用的是哈希函数，并且计算一个哈希值的时间是不受HashMap里的元素的个数的影响的。
　　示例2：线性搜索一个数组，列表以及链表都是的复杂度线性的，也即是O(n)，这是查找的时候需要遍历整个列表。也是说，如果一个列表的长度是原来的两倍，那么搜索所花的时间也是原来的两倍。
　　示例3：一个需要比较数组里的所有元素的排序算法的复杂度是多项式的，即是O(n^2)。这是因为一个嵌套的for循环的复杂度是O(n^2)。在搜素算法里有这样的例子。
　　示例4：二分搜索一个数组或者数组列表的复杂度是对数的，即是O(log n)。在链表里查询一个节点的复杂度一般是O(n)。相比较数组链表和数组的O(log n)的性能而言，随着元素数量的增长，链表的O(n)的复杂度的性能比较差了。对数的时间复杂度是如果10个元素花费的时间是x单位的话，100个元素多花费2x单位的时间，而10000个元素多花费4x个单位的时间。如果你在一个平面坐标上画出图形的话，你会发现时间的增长没有n（元素的个数）快。
　　Q：HashMap和TreeMap在性能上有什么样的差别呢？你比较倾向于使用哪一个?
　　A：一个平衡树的性能是O(logn)。Java里的TreeMap用一个红黑树来保证key/value的排序。红黑树是平衡二叉树。保证二叉树的平衡性，使得插入，删除和查找都比较快，时间复杂度都是O(log n)。不过它没有HashMap快，HashMap的时间复杂度是O(1)，但是TreeMap的优点在于它里面键值是排过序的，这样提供了一些其他的很有用的功能。