复制第一个孩子下一个兄弟姐妹树

问题描述：

我已经在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; 
}

如何使递归工作？

在此先感谢

答

明白了..

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; 
}

答

首先，我相信你这里有一个错误：

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

由于getNextSibling（）retuns下一个孩子的权利，但的addChild（）从插入儿童左边，你正在倒转这里的顺序。这可能是好的，但尽量避免这种情况。

要回答你的问题，应该在新树的每个节点上调用递归函数作为方法，并接收旧树的相应节点作为参数。然后它应该从新树中的旧树中复制此节点的子节点，并在执行此操作时，对每个这些子节点调用递归函数。

复制第一个孩子下一个兄弟姐妹树

相关推荐