遞回改寫成回圈方式的實作例子-樹的遍歷

結果

構造的樹為
          Tree001      
         /      \      
    Tree002     Tree003
       /               
 Tree004                

遞回方式遍歷一棵樹
第1次要遍歷的tree為：Tree{nodeId='001', nodeName='根結點'}
001:根結點
第2次要遍歷的tree為：Tree{nodeId='002', nodeName='結點2'}
002:結點2
第3次要遍歷的tree為：Tree{nodeId='004', nodeName='結點4'}
004:結點4
第4次要遍歷的tree為：Tree{nodeId='003', nodeName='結點3'}
003:結點3

回圈方式遍歷一棵樹
第1次要遍歷的tree為：[Tree{nodeId='001', nodeName='根結點'}]
001:根結點
第2次要遍歷的tree為：[Tree{nodeId='002', nodeName='結點2'}, Tree{nodeId='003', nodeName='結點3'}]
002:結點2
003:結點3
第3次要遍歷的tree為：[Tree{nodeId='004', nodeName='結點4'}]
004:結點4

代碼

樹的資料結構

package com.hdwang.test;

import java.util.List;

/**
 * 樹
 */
public class Tree {

    /**
     * 樹結點ID
     */
    private String nodeId;

    /**
     * 樹結點名稱
     */
    private String nodeName;

    /**
     * 孩子結點
     */
    private List<Tree> children;

    public String getNodeId() {
        return nodeId;
    }

    public void setNodeId(String nodeId) {
        this.nodeId = nodeId;
    }

    public String getNodeName() {
        return nodeName;
    }

    public void setNodeName(String nodeName) {
        this.nodeName = nodeName;
    }

    public List<Tree> getChildren() {
        return children;
    }

    public void setChildren(List<Tree> children) {
        this.children = children;
    }

    @Override
    public String toString() {
        return "Tree{" +
                "nodeId='" + nodeId + '\'' +
                ", nodeName='" + nodeName + '\'' +
                '}';
    }
}

遍歷程式

package com.hdwang.test;

import org.apache.commons.collections4.CollectionUtils;

import java.util.*;

/**
 * 遞回改成for回圈方式的例子
 */
public class RecursiveToForTest {

    /**
     * 記錄遍歷的次數
     */
    private static Long index = 0L;

    public static void main(String[] args) {
        //構造一顆樹
        Tree tree = buildTree();

        //遞回遍歷
        System.out.println("遞回方式遍歷一棵樹");
        recursivePrint(tree);

        //索引重置
        index = 0L;

        //回圈遍歷
        System.out.println("\n回圈方式遍歷一棵樹");
        forPrint(tree);
    }


    /**
     * 遞回方式列印輸出一棵樹
     *
     * @param tree 樹
     */
    private static void recursivePrint(Tree tree) {
        System.out.println("第" + (++index) + "次要遍歷的tree為：" + tree);
        System.out.println(tree.getNodeId() + ":" + tree.getNodeName());
        if (CollectionUtils.isNotEmpty(tree.getChildren())) {
            for (Tree child : tree.getChildren()) {
                recursivePrint(child);
            }
        }
    }

    /**
     * for回圈方式列印一顆樹
     *
     * @param tree 樹
     */
    private static void forPrint(Tree tree) {
        //使用串列存盤需要遍歷的樹結點
        List<Tree> treeList = new LinkedList<>();
        treeList.add(tree);
        //當需要遍歷的樹串列不為空時，一直遍歷輸出結點資訊
        while (CollectionUtils.isNotEmpty(treeList)) {
            System.out.println("第" + (++index) + "次要遍歷的tree為：" + treeList);
            List<Tree> waitToPrintTreeList = new ArrayList<>();
            for (Tree treeNode : treeList) {
                System.out.println(treeNode.getNodeId() + ":" + treeNode.getNodeName());

                //將孩子結點添加到待遍歷串列
                if (CollectionUtils.isNotEmpty(treeNode.getChildren())) {
                    waitToPrintTreeList.addAll(treeNode.getChildren());
                }
            }
            //移除已經遍歷過的樹結點
            treeList.clear();
            //將待遍歷樹結點添加到串列中
            treeList.addAll(waitToPrintTreeList);
        }
    }

    /**
     * 構造一顆樹
     *
     * @return 樹
     */
    private static Tree buildTree() {
        Tree tree001 = new Tree();
        tree001.setNodeId("001");
        tree001.setNodeName("根結點");

        List<Tree> childrenOf001 = new ArrayList<>();
        Tree tree002 = new Tree();
        tree002.setNodeId("002");
        tree002.setNodeName("結點2");
        childrenOf001.add(tree002);
        Tree tree003 = new Tree();
        tree003.setNodeId("003");
        tree003.setNodeName("結點3");
        childrenOf001.add(tree003);
        tree001.setChildren(childrenOf001);

        List<Tree> childrenOf002 = new ArrayList<>();
        Tree tree004 = new Tree();
        tree004.setNodeId("004");
        tree004.setNodeName("結點4");
        childrenOf002.add(tree004);
        tree002.setChildren(childrenOf002);

        System.out.println("構造的樹為");
        System.out.println("          Tree001      \n" +
                "\t\t /      \\      \n" +
                "\tTree002     Tree003\n" +
                "       /               \n" +
                " Tree004                ");
        System.out.println();
        return tree001;
    }
}

結語

晦澀難懂的程式邏輯，掌握了本質之后，便豁然開朗了！ 不管是遞回還是回圈本質都是：反復呼叫同一段代碼，遍歷的條件和待遍歷的資料需要考慮，遞回采用堆疊存盤記錄了待遍歷的資料，回圈只能自己去想辦法存盤待遍歷的資料，至于回圈條件都一樣，有則遍歷，無則罷了！

標籤：其他

上一篇：[NOIP1998 提高組] 拼數

下一篇：1003 我要通過！（20分）