递归返回树结构的结果
问题描述
给定一个树形结构的数据,目标是使用递归找到目标节点,并返回从根节点到目标节点的路径。
立即学习“Java免费学习笔记(深入)”;
import java.util.arraylist; import java.util.list; public class treenode { private string name; private list<treenode> children; public treenode(string name) { this.name = name; this.children = new arraylist<>(); } public void addchild(treenode child) { this.children.add(child); } public list<treenode> getchildren() { return children; } public string getname() { return name; } //使用递归算法查找目标节点,并返回从根节点到目标节点的路径 public list<treenode> findpath(string target) { if (this.name.equals(target)) { list<treenode> path = new arraylist<>(); path.add(this); return path; } else { for (treenode child : children) { list<treenode> path = child.findpath(target); if (path != null) { path.add(this); return path; } } } return null; } } public class main { public static void main(string[] args) { // 创建树形结构 treenode root = new treenode("三国"); treenode liubei = new treenode("刘备"); treenode liuyan = new treenode("刘焉"); treenode sunjian = new treenode("孙坚"); treenode caocao = new treenode("曹操"); root.addchild(liubei); root.addchild(liuyan); root.addchild(sunjian); root.addchild(caocao); // 在刘备下添加子节点 treenode liufeng = new treenode("刘封"); treenode liushan = new treenode("刘禅"); liubei.addchild(liufeng); liubei.addchild(liushan); // 在刘焉下添加子节点 treenode liuzhang = new treenode("刘璋"); liuyan.addchild(liuzhang); // 在刘璋下添加子节点 treenode liuxun = new treenode("刘循"); liuzhang.addchild(liuxun); // 在孙坚下添加子节点 treenode sunce = new treenode("孙策"); treenode sunquan = new treenode("孙权"); sunjian.addchild(sunce); sunjian.addchild(sunquan); // 在曹操下添加子节点 treenode caopi = new treenode("曹丕"); treenode caozhi = new treenode("曹植"); treenode caozhang = new treenode("曹彰"); treenode qinlang = new treenode("秦朗"); caocao.addchild(caopi); caocao.addchild(caozhi); caocao.addchild(caozhang); caocao.addchild(qinlang); // 使用递归算法查找目标节点 list<treenode> path = root.findpath("孙策"); // 打印从根节点到目标节点的路径 for (treenode node : path) { system.out.println(node.getname()); } } }
代码解释
- 创建树形结构:创建一个treenode对象作为根节点,然后在根节点下添加子节点。
- 查找目标节点:使用递归算法遍历树形结构,如果当前节点的名称等于目标,则返回当前节点。否则,遍历子节点,如果子节点中找到目标节点,则将子节点的路径加上当前节点,并返回。
- 打印路径:遍历查找出来的路径,打印每个节点的名称。
运行结果
三国 孙坚 孙策