当前位置: 老葡京网站娱乐 > 编程语言 > 算法 > 正文

树的遍历

时间:2012-03-08 BlogJava Jiangshachina

老葡京网站娱乐 www.sdguanhua.com 之前的工作都没有接触到树,也就很少研究它。幸运地的是,在目前的工作中多次遇到树型结构的数据,那么访问树节点中的数据就是必然的了,而且还需要按照指定规则对节点中的数据进行额外处理。经过学习之后,对与树相关的基本算法有了一些认知,就计划写几篇小文。其实这样的文章早已是汗牛充栋,而我只是把它当作我的学习总结罢了,以加深记忆与理解,如能对其他朋友有所助益,则更感愉悦了 :-) (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();

}