乐趣区

多叉树全路径遍历

jiezi

多叉树全路径遍历

本文为原创作品，首发于微信公众号：【坂本先生】，如需转载请在文首明显位置标明“转载于微信公众号：【坂本先生】”，否则追究其法律责任。

前言

本文研究的是如何对一个多叉树进行全路径的遍历，并输出全路径结果。该问题的研究可以用在：Trie 树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现，讨论了递归和非递归两种方法优劣并分别进行实现，如果读者对这两种方法的优劣不感兴趣可直接跳到 问题构建 章节进行阅读。文章较长，推荐大家先收藏再进行阅读。

文章目录

  • 多叉树全路径遍历

    • 前言
    • 文章目录

    • 递归和迭代比较

      • 递归
      • 迭代

      • 递归的劣势和优势

        • 递归的劣势
        • 递归的优势
    • 问题构建

    • 问题解决

      • 递归方法
      • 迭代方法
    • 结论
    • 参考资料

递归和非递归比较

这个问题知乎上已经有了很多答案（https://www.zhihu.com/questio…），在其基础上我进行了一波总结：

递归

将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。

非递归

执行效率高，运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加

递归的劣势和优势

递归的劣势

  • 递归容易产生 ” 栈溢出 ” 错误（stack overflow）。因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。
  • 效率方面，递归可能存在冗余计算。使用递归的方式会有冗余计算（比如最典型的是斐波那契数列，计算第 6 个需要计算第 4 个和第 5 个，而计算第 5 个还需要计算第 4 个，所处会重复）。迭代在这方面有绝对优势。

递归的优势

递归拥有较好的代码可读性，对于数据量不算太大的运算，使用递归算法绰绰有余。

问题构建

现在存在一个多叉树，其结点情况如下图，需要给出方法将叶子节点的所有路径进行输出。

最终输出结果应该有 5 个，即[rad,rac,rbe,rbf,rg]

问题解决

首先我们对结点进行分析，构建一个结点类（TreeNode），然后我们需要有一个树类（MultiTree），包含了全路径打印的方法。最后我们需要建立一个 Main 方法进行测试。最终的项目结构如下：

注意：本文使用了 lombok 注解，省去了 get，set 及相关方法的实现。如果读者没有使用过 lombok 也可以自己编写对应的 get，set 方法，后文会对每个类进行说明需要进行实现的方法，对核心代码没有影响。

TreeNode 类

节点类，主要包含两个字段：

  • content：用于存储当前节点存储的内容
  • childs：用于存储子节点信息，HashMap 的 string 存储的是子节点内容，childs 采用 HashMap 实现有利于实现子节点快速查找

该类中包含了必要的 get，set 方法，一个无参构造器，一个全参构造器

@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
    private String content;
    private HashMap<String,TreeNode> childs;
}

MultiTree 类

包含的字段只有两个：

  • root：根节点
  • pathList：用于存储遍历过程中得到的路径

该类中的构造函数中我手动创建问题构建中的树，相关代码如下：

    public MultiTree(){
        // 创建根节点
        HashMap rootChilds = new HashMap();
        this.root = new TreeNode("r",rootChilds);

        // 第一层子节点
        HashMap aChilds = new HashMap();
        TreeNode aNode = new TreeNode("a",aChilds);

        HashMap bChilds = new HashMap();
        TreeNode bNode = new TreeNode("b",bChilds);

        HashMap gChilds = new HashMap();
        TreeNode gNode = new TreeNode("g",gChilds);

        // 第二层结点
        HashMap dChilds = new HashMap();
        TreeNode dNode = new TreeNode("d",dChilds);

        HashMap cChilds = new HashMap();
        TreeNode cNode = new TreeNode("c",cChilds);

        HashMap eChilds = new HashMap();
        TreeNode eNode = new TreeNode("e",eChilds);

        HashMap fChilds = new HashMap();
        TreeNode fNode = new TreeNode("f",fChilds);

        // 建立结点联系
        rootChilds.put("a",aNode);
        rootChilds.put("b",bNode);
        rootChilds.put("g",gNode);

        aChilds.put("d",dNode);
        aChilds.put("c",cNode);

        bChilds.put("e",eNode);
        bChilds.put("f",fNode);
    }

在这个树中，每个节点都有 childs，如果是叶子节点，则 childs 中的 size 为 0 ，这是下面判断一个节点是否为叶子节点的重要依据接下来我们会对核心算法代码进行实现。

Main 类

public class Main {public static void main(String[] args) {MultiTree tree = new MultiTree();
        List<String> path1 = tree.listAllPathByRecursion();
        System.out.println(path1);
        List<String> path2 = tree.listAllPathByNotRecursion();
        System.out.println(path2);
    }
}

递归方法

需要完善 MultiTree 类中的 listAllPathByRecursion 方法和 listPath 方法

递归过程方法：listAllPathByRecursion

算法流程图如下：

代码实现如下：

public void listPath(TreeNode root,String path){if(root.getChilds().isEmpty()){// 叶子节点
        path = path + root.getContent();
        pathList.add(path); // 将结果保存在 list 中
        return;
    }else{ // 非叶子节点
        path = path  + root.getContent() + "->";

        // 进行子节点的递归
        HashMap<String, TreeNode> childs = root.getChilds();
        Iterator iterator = childs.entrySet().iterator();
        while(iterator.hasNext()){Map.Entry entry = (Map.Entry)iterator.next();
            TreeNode childNode  = (TreeNode) entry.getValue();
            listPath(childNode,path);
        }
    }
}

递归调用方法：listAllPathByRecursion

public List<String> listAllPathByRecursion(){
    // 清空路径容器
    this.pathList.clear();
    listPath(this.root,"");
    return this.pathList;
}

非递归方法

非递归方法的代码量和递归方法一比，简直是太多了，而且内容不好理解，不知道大家能不能看懂我写的代码，我已经尽力写上相关注释了。

首先建立了两个栈，示意图如下，栈的实现使用 Deque，需要注意的是代码中的空指针情况。

  • 主栈：用于处理节点和临时路径的存储，主栈为空时说明，节点处理完毕
  • 副栈：用于存放待处理节点，副栈为空时说明，节点遍历完毕

其他相关变量介绍：

  • popCount：用于存储一个节点的子节点的弹出个数。例如 r 有 3 个子节点，如果 r 对应的弹出个数为 3，说明 r 的叶子节点处理完毕，可以弹出 r。因为 r 弹出后，主栈没有元素，故处理完毕。
  • curString：用于存储临时路径，当主栈元素变化时，curString 也会进行变化，例如上图 curString 为“r->g->”，当栈顶元素弹出时，需要减去 ”g->”。如果栈顶元素是叶子节点说明该条路径已经遍历完成，需要添加到 path 路径容器中。

程序流程图：

具体实现代码如下：

/**
 * 非递归方法输出所有路径
 */
public List<String> listAllPathByNotRecursion(){
    // 清空路径容器
    this.pathList.clear();
    // 主栈，用于计算处理路径
    Deque<TreeNode> majorStack = new ArrayDeque();
    // 副栈，用于存储待处理节点
    Deque<TreeNode> minorStack = new ArrayDeque();
    minorStack.addLast(this.root);

    HashMap<String,Integer> popCount = new HashMap<>();
    String curString  = "";

    while(!minorStack.isEmpty()){
        // 出副栈，入主栈
        TreeNode minLast = minorStack.pollLast();
        majorStack.addLast(minLast);
        curString+=minLast.getContent()+"->";
        // 将该节点的子节点入副栈
        if(!minLast.getChilds().isEmpty()){HashMap<String, TreeNode> childs = minLast.getChilds();
            Iterator iterator = childs.entrySet().iterator();
            while(iterator.hasNext()){Map.Entry entry = (Map.Entry)iterator.next();
                TreeNode childNode  = (TreeNode) entry.getValue();
                minorStack.addLast(childNode);
            }
        }
        // 出主栈
        TreeNode majLast = majorStack.peekLast();
        // 循环条件：栈顶为叶子节点 或 栈顶节点孩子节点遍历完了（需要注意空指针问题）while(majLast.getChilds().size() ==0 ||
                (popCount.get(majLast.getContent())!=null && popCount.get(majLast.getContent()).equals(majLast.getChilds().size()))){TreeNode last = majorStack.pollLast();
            majLast = majorStack.peekLast();

            if(majLast == null){ // 此时主栈为空，运算完毕
                return this.pathList;
            }
            if(popCount.get(majLast.getContent())==null){// 第一次弹出孩子节点，弹出次数设为 1
                popCount.put(majLast.getContent(),1);
            }else{ // 非第一次弹出孩子节点，在原有基础上加 1
                popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
            }
            String lastContent = last.getContent();
            if(last.getChilds().isEmpty()){// 如果是叶子节点才将结果加入路径集中
                this.pathList.add(curString.substring(0,curString.length()-2));
            }
            // 调整当前 curString，减去 2 是减的“->”这个符号
            curString = curString.substring(0,curString.length()-lastContent.length()-2);
        }
    }
    return this.pathList;
}

测试

调用 Main 类中的 main 方法，得到执行结果，和预期结果相同，代码通过测试

listAllPathByRecursion[r->a->c, r->a->d, r->b->e, r->b->f, r->g]
listAllPathByNotRecursion[r->g, r->b->f, r->b->e, r->a->d, r->a->c]

结论

其实该文章是我在研究《基于 Trie 树的敏感词过滤算法实现》的一个中间产物，其实原来应该也实现过多叉树的路径遍历问题，但是因为时间原因加之原来没有较好的知识管理系统，代码和笔记都丢了，今天趁机再进行一波总结。希望该文章能够帮助到需要的人。

参考资料

  • [递归」和「迭代」有哪些区别？– 叶世清的回答 – 知乎
  • 递归如何转换为非递归
退出移动版