1

我正在编写一个程序，该程序需要输入一些名称并查看以下结构的树：

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /   |   \        |  \
                                               Tom Ben  Anna    Jade  Ed
                                               /  \      |           /  \
                                            Will  Mark  Ant        Andy  Dan

程序应该返回根节点是输入名称之间最低关系/链接的子树。

如果我输入 Mark 和 Ant，程序应该返回以下树：

                                                  Chris 
                                                /       \   
                                               Tom     Anna     
                                                  \      |         
                                                  Mark  Ant

如果我输入 Will、Mark 和 Andy，那么程序应该返回以下树：

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /                   \
                                               Tom                   Ed
                                               /  \                  /  
                                            Will  Mark             Andy

我正在为我的树节点和连接使用以下类：

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

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

    public Person(String name) { 
        this.name = name; 
        children = new ArrayList<Person>();
    }

    public String getName() {
        return name;
    }
    public List<Person> getChildren() {
        return children;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setChildren(List<Person> children) {
        this.children = children;
    }
    public void addChild(Person c) { 
        children.add(c);
    }
}

我的问题是如何解决确定公共节点的问题（首先是 Chris，其次是 John）以及如何使用该名称来获取子树（公共节点和下面的节点）。

我也在考虑对此进行扩展以使用 Neo4j 数据库，但想先在这种情况下解决它。

谢谢！

4

1 回答 1

1

您正在寻找的是最低的共同祖先：

http://en.wikipedia.org/wiki/Lowest_common_ancestor

我可以尝试详细解释它，但我永远不会比本教程做得更好、更全面，它教给你许多不同的算法来解决这个问题：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

于 2012-10-23T23:44:25.000 回答