Hello! 欢迎来到小浪资源网!


Java递归算法如何查找树形结构中的目标节点并返回路径?


Java递归算法如何查找树形结构中的目标节点并返回路径?

递归返回树结构的结果

Java中,可以使用递归算法遍历树形结构并返回结果。

问题描述

给定一个树形结构的数据,目标是使用递归找到目标节点,并返回从根节点到目标节点的路径。

立即学习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对象作为根节点,然后在根节点下添加子节点。
  • 查找目标节点:使用递归算法遍历树形结构,如果当前节点的名称等于目标,则返回当前节点。否则,遍历子节点,如果子节点中找到目标节点,则将子节点的路径加上当前节点,并返回。
  • 打印路径:遍历查找出来的路径,打印每个节点的名称。

运行结果

三国 孙坚 孙策

相关阅读