树的遍历

树的遍历2012-03-08 BlogJava Jiangshachina之前的工作都没有接触到树，也就很少研究它。幸运地的是，在目前的工作中多次遇到树型结构的数据，那么访问树节点中的数据就是必然的了，而且还需要按照指定规则对节点中的数据进行额外处理。经过学习之后，对与树相关的基本算法有了一些认知，就计划写几篇小文。其实这样的文章早已是汗牛充栋，而我只是把它当作我的学习总结罢了，以加深记忆与理解，如能对其他朋友有所助益，则更感愉悦了 :-）（2009.04.01最后更新）

这次先从最基础的开始--树的遍历。本文使用了两种极常用的方法来遍历树中的所有节点--递归；迭代，但它们实现的都是深度优先（Depth-First）算法。

1. 树节点与数据

先定义树节点及数据（用户对象），并创建测试用的数据。

TreeNode是树节点的定义。

/** * 树节点的定义。 */public interface TreeNode {    /**     * 获取指定下标处的子节点。     *      * @param index     *            下标。     * @return 子节点。     */    public TreeNode getChildAt（int index）;    /**     * 返回指定子节点的下标。     *      * @param index     *            下标。     * @return 子节点。     */    public int getChildIndex（TreeNode index）;    /**     * 获取子节点的数量。     *      * @return 子节点的数量。     */    public int getChildCount（）;    /**     * 返回父节点。     *      * @return 父节点。     */    public TreeNode getParent（）;    /**     * 设置父节点。注：此处不需要改变父节点中的子节点元素。     *      * @param parent     *            父节点。     */    public void setParent（TreeNode parent）;    /**     * 获取所有的子节点。     *      * @return 子节点的集合。     */    public List<？> getChildren（）;    /**     * 是否为叶节点。     *      * @return 是叶节点，返回true；否则，返回false。     */    public boolean isLeaf（）;}