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、2 番目の例では 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 に答える