0

Javaで「最初の子の次の兄弟」ツリーのクラスを実装しました。

ここにそのようなツリーを表すリンクがあります

http://www.cs.utexas.edu/~novak/cs315116.html

以下の機能を実装しました。

addChild();
getLabel(); 
setLabel(T v);
getParent();
getNextSibling();
getFirstChild();

私の addChild 関数は、次の順序で子を追加します。

public void addChild(Tree<T> c) {
     c.parent = this;
     if (firstChild == null) 
       firstChild = c;
     else {
         c.nextSibling = firstChild;
         firstChild = c;
        }
}

That is, if we have a tree node 1 and we add tree node 2 and then tree node 3 to it then the final tree would be,
1.addChild(2);
1.addChild(3);

 1                                          1
/ \    which is internally stored as       /
3   2                                      3 - 2
The most recent child added would be the first child

そのようなツリーを引数として指定すると、ツリーのコピーを作成して返す CopyTree 関数を実装したいと考えています。初期コードはいくつかありますが、正しい再帰を取得できません。

private Tree<String> CopyTree(Tree<String> tr){
if (tr == null)
    return null;
Tree<String> t = new Tree<String>();
t.setLabel(tr.getLabel());
if (tr.getFirstChild() != null) {
    t.addChild(CopyTree(tr.getFirstChild()));
}
Tree<String> temp = tr.left();

if (temp != null) {
while (temp.getNextSibling() != null) {
    t.addChild(CopyTree(temp.getNextSibling()));
    temp = temp.getNextSibling();
}
}
return t;
}

再帰を機能させるために何をすべきか??

前もって感謝します

4

2 に答える 2

0

まず第一に、私はあなたがここでエラーを持っていると信じています：

 while (temp.getNextSibling() != null) {
    t.addChild(CopyTree(temp.getNextSibling()));
    temp = temp.getNextSibling();
}

getNextSibling（）は次の子を右に戻しますが、addChild（）は左から子を挿入するため、ここでは順序を逆にします。これは問題ないかもしれませんが、これは避けてください。

質問に答えるには、再帰関数を新しいツリーの各ノードでメソッドとして呼び出し、古いツリーの対応するノードを引数として受け取る必要があります。次に、このノードの子を新しいツリーの古いツリーからコピーし、これを実行しながら、これらの子のそれぞれで再帰関数を呼び出す必要があります。

于 2012-10-18T20:49:47.653 に答える
0

とった..

private Tree<String> CopyTree(Tree<String> tr){
if (tr == null)
    return null;
Tree<String> t = new Tree<String>();
t.setLabel(tr.getLabel());

Tree<String> temp = tr.left();

if (temp != null) {
    ArrayList<Tree<String>> list = new ArrayList<>();
    while (temp.getNextSibling() != null) {
    list.add(temp.getNextSibling());
    //t.addChild(CopyTree(temp.getNextSibling()));
    temp = temp.getNextSibling();
}
for (int i = (list.size()-1); i>=0; i--) {
    t.addChild(CopyTree(list.get(i)));
}

}
if (tr.left() != null) {
    t.addChild(CopyTree(tr.left()));
}

return t;
}
于 2012-10-18T21:56:08.057 に答える