樹的遍歷(轉載)

樹的遍歷

之前的工作都沒有接觸到樹，也就很少研究它。幸運地的是，在目前的工作中多次遇到樹型結構的數據，那么訪問樹節點中的數據就是必然的了，而且還需要按照指定規則對節點中的數據進行額外處理。經過學習之后，對與樹相關的基本算法有了一些認知，就計劃寫幾篇小文。其實這樣的文章早已是汗牛充棟，而我只是把它當作我的學習總結罷了，以加深記憶與理解，如能對其他朋友有所助益，則更感愉悅了 :-) (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-06-05 16:57 chencx 閱讀(81) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

My Links

Blog Stats

留言簿

隨筆分類

文章分類

文章檔案

搜索

最新評論

樹的遍歷(轉載)