您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
本文为原创作品，首发于微信公众号：【坂本先生】，如需转载请在文首明显位置标明“转载于微信公众号：【坂本先生】”，否则追究其法律责任。
微信文章地址：实战算法——多叉树全路径遍历
本文研究的是如何对一个多叉树进行全路径的遍历，并输出全路径结果。该问题的研究可以用在：Trie树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现，讨论了递归和非递归两种方法优劣并分别进行实现，如果读者对这两种方法的优劣不感兴趣可直接跳到问题构建章节进行阅读。文章较长，推荐大家先收藏再进行阅读。
这个问题知乎上已经有了很多答案，https://www.zhihu.com/question/20278387
在其基础上我进行了一波总结：
将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。
执行效率高，运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加
递归容易产生"栈溢出"错误（stack overflow）。因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。
递归拥有较好的代码可读性，对于数据量不算太大的运算，使用递归算法绰绰有余。
现在存在一个多叉树，其结点情况如下图，需要给出方法将叶子节点的所有路径进行输出。
最终输出结果应该有5个，即[rad,rac,rbe,rbf,rg]
首先我们对结点进行分析，构建一个结点类（TreeNode），然后我们需要有一个树类（MultiTree），包含了全路径打印的方法。最后我们需要建立一个Main方法进行测试。最终的项目结构如下：
注意：本文使用了lombok注解，省去了get，set及相关方法的实现。如果读者没有使用过lombok也可以自己编写对应的get，set方法，后文会对每个类进行说明需要进行实现的方法，对核心代码没有影响。
TreeNode类
节点类，主要包含两个字段：
该类中包含了必要的get，set方法，一个无参构造器，一个全参构造器
@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
private String content;
private HashMap<String,TreeNode> childs;
}MultiTree类
包含的字段只有两个：
该类中的构造函数中我手动创建问题构建中的树，相关代码如下：
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> path2 = tree.listAllPathByRecursion();
System.out.println(path2);
List<String> path3 = tree.listAllPathByNotRecursion();
System.out.println(path3);
}
}需要完善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，需要注意的是代码中的空指针情况。
主栈：用于处理节点和临时路径的存储，主栈为空时说明，节点处理完毕
副栈：用于存放待处理节点，副栈为空时说明，节点遍历完毕
其他相关变量介绍：
程序流程图：
具体实现代码如下：
/**
* 非递归方法输出所有路径
*/
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树的敏感词过滤算法实现》的一个中间产物，其实原来应该也实现过多叉树的路径遍历问题，但是因为时间原因加之原来没有较好的知识管理系统，代码和笔记都丢了，今天趁机再进行一波总结。希望该文章能够帮助到需要的人。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。