获取树的所有分支的方法

Question

我有一个来自这个的对象 Class:

public class Person{
    private String name;
    private List<Person> children;
}

我想写 JAVA 方法：private List extractNames(Person ancestor) 它返回树的每个分支的所有名称：

你有什么想法，我该怎么做？

Answer 1

我对 Java 不是很擅长，但这里是您想要在 Python 中执行的操作的代码。只需将 extractNames 方法转换为 Java.

class Person:
    def __init__(self, name, children=[]):
        self.name = name
        self.children = children
        
personD = Person("D", [])
personE = Person("E", [])
personF = Person("F", [])

personB = Person("B", [personD,personE,personF])

personG = Person("G", [])
personH = Person("H", [])

personC = Person("C", [personG, personH])

personA = Person("A", [personB,personC])

def extractNames(personHead, branchStack):
    # Keep adding children to branch stack
    branchStack.append(personHead.name)
    if len(personHead.children) == 0:
        print(branchStack)
    for child in personHead.children:
        extractNames(child,branchStack)
        # After going till all children we will remove everything till the parent
        while (branchStack[-1] != personHead.name):
            branchStack.pop(-1)
    return
    
extractNames(personA,branchStack=[])

'''
Output: 
['A', 'B', 'D']
['A', 'B', 'E']
['A', 'B', 'F']
['A', 'C', 'G']
['A', 'C', 'H']
'''

Answer 2

更新：移除了对 lombok 的依赖

相关算法部分在classPersonGetNamesTest的extractNamesAlternative方法中。其余代码只是一些糖，因此可以运行与 junit。如果你不会junit怎么用，把方法extractNamesAlternative复制到你自己的class.

Person.java

import java.util.ArrayList;
import java.util.List;

public class Person {

    private String name;
    private List<Person> children = new ArrayList<>();

    Person(String name, List<Person> children){
        this.name = name;
        this.children = children;
    }
    
    Person(String name){
        this.name = name;
    }

    public String getName(){
        return name;
    }

    public List<Person> getChildren(){
        return children;
    }
}

ExtractNamesTest.java

import org.assertj.core.util.Lists;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class ExtractNamesTest {

    @Test
    void testPersonGetNamesTest() {
        Person personD = new Person("D");
        Person personE = new Person("E");
        Person personF = new Person("F");

        Person personB = new Person("B", Arrays.asList(personD, personE, personF));
        Person personG = new Person("G");
        Person personH = new Person("H");

        Person personC = new Person("C", Arrays.asList(personG, personH));
        
        Person personA = new Person("A", Arrays.asList(personB, personC));


        List<String> namesAlternative = extractNamesAlternative(personA, new ArrayList<>(), new ArrayList<>());
        assertEquals(Lists.list(
                "ABD", "ABE", "ABF", "ACG", "ACH"),
                namesAlternative);
    }

    private List<String> extractNamesAlternative(Person ancestor, List<String> names, List<Person> allAncestors) {
        allAncestors.add(ancestor);
        if (ancestor.getChildren().isEmpty()) {
            names.add(allAncestors.stream().map(Person::getName).collect(Collectors.joining()));
            return names;
        } else {
            for (Person p : ancestor.getChildren()) {
                extractNamesAlternative(p, names, new ArrayList<Person>(allAncestors));
            }
        }
        return names;
    }
}

Answer 3

在这里我展示了我是如何实现这个功能的：

private static void extractNames(Person ancestor, String branchName, List<String> listBranch){
    if(ancestor.getChildren().size()>0) {
        branchName = branchName + ancestor.getName() + ",";
        for(int i=0; i<ancestor.getChildren().size(); i++) {                
            extractNames(ancestor.getChildren().get(i), branchName, listBranch);                
        }
    }else {
        branchName = branchName + ancestor.getName();
        listBranch.add(branchName);
    }
}

以及如何从 main 调用它：

public static void main(String[] args) {
    //Create persons
    Person pA = new Person("A");
    Person pB = new Person("B");
    Person pC = new Person("C");
    Person pD = new Person("D");
    Person pE = new Person("E");
    Person pF = new Person("F");
    Person pG = new Person("G");
    Person pH = new Person("H");
    
    //Assign children
    pA.addChildren(pB);
    pA.addChildren(pC);
    pB.addChildren(pD);
    pB.addChildren(pE);
    pB.addChildren(pF);
    pC.addChildren(pG);
    pC.addChildren(pH);
    
    List<String> branchList = new ArrayList<String>();
    //call      
    extractNames(pA, "", branchList);
    //print list
    for(int i=0;i<branchList.size();i++) {
        System.out.println(branchList.get(i));
    }
}

希望对你有所帮助。

获取树的所有分支的方法

Method to get all the branches of a tree

java

data-structures