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

霞舞 2024-11-30 00:00:00 次阅读

递归返回树结构的结果

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

问题描述

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

解决方法

import java.util.arraylist;
import java.util.list;

public class treenode {
    private string name;
    private list children;

    public treenode(string name) {
        this.name = name;
        this.children = new arraylist<>();
    }

    public void addchild(treenode child) {
        this.children.add(child);
    }

    public list getchildren() {
        return children;
    }

    public string getname() {
        return name;
    }

    //使用递归算法查找目标节点，并返回从根节点到目标节点的路径
    public list findpath(string target) {
        if (this.name.equals(target)) {
            list path = new arraylist<>();
            path.add(this);
            return path;
        } else {
            for (treenode child : children) {
                list 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 path = root.findpath("孙策");

        // 打印从根节点到目标节点的路径
        for (treenode node : path) {
            system.out.println(node.getname());
        }
    }
}