首页 > Java > java教程 > 正文

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

霞舞
发布: 2024-11-30 19:21:30
原创
1192人浏览过

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

递归返回树结构的结果

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

问题描述

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

立即学习Java免费学习笔记(深入)”;

慧中标AI标书
慧中标AI标书

慧中标AI标书是一款AI智能辅助写标书工具。

慧中标AI标书 120
查看详情 慧中标AI标书

解决方法

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

运行结果

三国
孙坚
孙策
登录后复制

以上就是Java递归算法如何查找树形结构中的目标节点并返回路径?的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门推荐
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号