John Jiang

a cup of Java, cheers!
https://github.com/johnshajiang/blog

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

这次先从最基础的开始--树的遍历。本文使用了两种极常用的方法来遍历树中的所有节点--递归;迭代,但它们实现的都是深度优先(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();
}

GenericTreeNode是一个通用的树节点实现。
public class GenericTreeNode<T> implements TreeNode {

    
private T userObject = null;

    
private TreeNode parent = null;

    
private List<GenericTreeNode<T>> children = new ArrayList<GenericTreeNode<T>>();

    
public GenericTreeNode(T userObject) {
        
this.userObject = userObject;
    }

    
public GenericTreeNode() {
        
this(null);
    }

    
/**
     * 添加子节点。
     * 
     * 
@param child
     
*/
    
public void addChild(GenericTreeNode<T> child) {
        children.add(child);
        child.setParent(
this);
    }

    
/**
     * 删除指定的子节点。
     * 
     * 
@param child
     *            子节点。
     
*/
    
public void removeChild(TreeNode child) {
        removeChildAt(getChildIndex(child));
    }

    
/**
     * 删除指定下标处的子节点。
     * 
     * 
@param index
     *            下标。
     
*/
    
public void removeChildAt(int index) {
        TreeNode child 
= getChildAt(index);
        children.remove(index);
        child.setParent(
null);
    }

    
public TreeNode getChildAt(int index) {
        
return children.get(index);
    }

    
public int getChildCount() {
        
return children.size();
    }

    
public int getChildIndex(TreeNode child) {
        
return children.indexOf(child);
    }

    
public List<GenericTreeNode<T>> getChildren() {
        
return Collections.unmodifiableList(children);
    }

    
public void setParent(TreeNode parent) {
        
this.parent = parent;
    }

    
public TreeNode getParent() {
        
return parent;
    }

    
/**
     * 是否为根节点。
     * 
     * 
@return 是根节点,返回true;否则,返回false。
     
*/
    
public boolean isRoot() {
        
return getParent() == null;
    }

    
public boolean isLeaf() {
        
return getChildCount() == 0;
    }

    
/**
     * 判断指定的节点是否为当前节点的子节点。
     * 
     * 
@param node
     *            节点。
     * 
@return 是当前节点的子节点,返回true;否则,返回false。
     
*/
    
public boolean isChild(TreeNode node) {
        
boolean result;
        
if (node == null) {
            result 
= false;
        } 
else {
            
if (getChildCount() == 0) {
                result 
= false;
            } 
else {
                result 
= (node.getParent() == this);
            }
        }

        
return result;
    }

    
public T getUserObject() {
        
return userObject;
    }

    
public void setUserObject(T userObject) {
        
this.userObject = userObject;
    }

    @Override
    
public String toString() {
        
return userObject == null ? "" : userObject.toString();
    }
}

UserObject是节点上的用户对象,相当于是数据。
public class UserObject {

    
private String name = null;

    
private Integer value = Integer.valueOf(0);

    
public UserObject() {

    }

    
public UserObject(String code, Integer value) {
        
this.name = code;
        
this.value = value;
    }

    
public String getName() {
        
return name;
    }

    
public void setName(String code) {
        
this.name = code;
    }

    
public Integer getValue() {
        
return value;
    }

    
public void setValue(Integer value) {
        
this.value = value;
    }

    @Override
    
public String toString() {
        StringBuilder result 
= new StringBuilder();
        result.append(
"[name=").append(name).append(", value=").append(value).append("]");
        
return result.toString();
    }
}

TreeUtils是用于创建树的工具类。
public class TreeUtils {

    
public static GenericTreeNode<UserObject> buildTree() {
        GenericTreeNode
<UserObject> root = new GenericTreeNode<UserObject>();
        root.setUserObject(
new UserObject("ROOT", Integer.valueOf(0)));

        GenericTreeNode
<UserObject> node1 = new GenericTreeNode<UserObject>();
        node1.setUserObject(
new UserObject("1", Integer.valueOf(0)));
        GenericTreeNode
<UserObject> node2 = new GenericTreeNode<UserObject>();
        node2.setUserObject(
new UserObject("2", Integer.valueOf(0)));
        GenericTreeNode
<UserObject> node3 = new GenericTreeNode<UserObject>();
        node3.setUserObject(
new UserObject("3", Integer.valueOf(5)));

        root.addChild(node1);
        root.addChild(node2);
        root.addChild(node3);

        GenericTreeNode
<UserObject> node11 = new GenericTreeNode<UserObject>();
        node11.setUserObject(
new UserObject("11", Integer.valueOf(0)));
        GenericTreeNode
<UserObject> node21 = new GenericTreeNode<UserObject>();
        node21.setUserObject(
new UserObject("21", Integer.valueOf(0)));

        node1.addChild(node11);
        node2.addChild(node21);

        GenericTreeNode
<UserObject> node111 = new GenericTreeNode<UserObject>();
        node111.setUserObject(
new UserObject("111", Integer.valueOf(3)));
        GenericTreeNode
<UserObject> node112 = new GenericTreeNode<UserObject>();
        node112.setUserObject(
new UserObject("112", Integer.valueOf(9)));
        GenericTreeNode
<UserObject> node211 = new GenericTreeNode<UserObject>();
        node211.setUserObject(
new UserObject("211", Integer.valueOf(6)));
        GenericTreeNode
<UserObject> node212 = new GenericTreeNode<UserObject>();
        node212.setUserObject(
new UserObject("212", Integer.valueOf(3)));

        node11.addChild(node111);
        node11.addChild(node112);
        node21.addChild(node211);
        node21.addChild(node212);

        
return root;
    }
}

2. 递归法
使用递归法的最大好处就是--简单,但一般地,我们都认为递归的效率不高。
private static void recursiveTravel(GenericTreeNode<UserObject> node) {
    travelNode(node); 
// 访问节点,仅仅只是打印该节点罢了。
    List<GenericTreeNode<UserObject>> children = node.getChildren();
    
for (int i = 0; i < children.size(); i++) {
        recursiveTravel(children.get(i)); 
// 递归地访问当前节点的所有子节点。
    }
}
大家肯定知道,系统在执行递归方法(对于其它方法也是如此)时是使用运行时栈。对方法的每一次调用,在栈中都会创建一份此次调用的活动记录--包括方法的参数,局部变量,返回地址,动态链接库,返回值等。
既然系统能够隐式地使用栈去执行递归方法,那么我们就可以显式地使用栈来执行上述递归程序,这也是将递归程序转化为迭代程序的常用思想。下面的iterativeTravel方法就运用了这一思想。

3. 迭代法
private static void iterativeTravel(GenericTreeNode<UserObject> node) {
    Stack
<GenericTreeNode<UserObject>> nodes = new Stack<GenericTreeNode<UserObject>>();

    nodes.push(node); 
// 将当前节点压入栈中。
    while (!nodes.isEmpty()) {
        GenericTreeNode
<UserObject> bufNode = nodes.pop(); // 从栈中取出一个节点。
        travelNode(bufNode); // 访问节点。
        if (!bufNode.isLeaf()) { // 如果该节点为分枝节点,则将它的子节点全部加入栈中。
            nodes.addAll(bufNode.getChildren());
        }
    }
}
与递归法相比,迭代法的代码略多了几行,但仍然很简单。

4. 小结
由于上述两种方法均(隐式或显式地)使用了运行栈,所以此处的迭代法并不能提高整个程序的效率。相反地,由于在应用程序中显式地使用栈(java.util.Stack),iterativeTravel方法的效率可能反而更低。但iterativeTravel的最大好处是,能够有效地避免运行时栈溢出(java.lang.StackOverflowError)。
如果树的层次不太深,每层的子节点数不太多,那么使用递归法应该是没有问题的。毕竟,简洁地程序会提供更多的好处。

posted on 2009-04-01 20:40 John Jiang 阅读(5283) 评论(4)  编辑  收藏 所属分类: JavaAlgorithm原创

评论

# re: 树的遍历(原)[未登录] 2009-04-03 08:59 GreatGhoul
很喜欢你的文章,学习这个迭代算法.  回复  更多评论
  

# re: 树的遍历(原) 2009-04-03 21:37 Sha Jiang
嘿嘿,谢谢!
我也逛了一下你的blogspot  回复  更多评论
  

# re: 树的遍历(原) 2010-07-27 22:19 Salazar
看了你的迭代的方法,实现的应该是广度优先,STACK-FIFO原理,拿二叉树举例,先访问根节点(将左右节点入栈),然后访问左节点(左节点的子节点入栈),然后是访问右节点(右节点的子节点入栈),接下来就是同上顺序。  回复  更多评论
  

# re: 树的遍历(原) 2010-08-26 20:11 Sha Jiang
@Salazar
对于深度优先算法,正是使用栈;而对于广度优先算法,则应该使用队列。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: