我想用我自己的Node类在Java中实现树状结构。 但我很困惑，如何做一个深拷贝复制树。
我的节点类将是这样的：
public class Node{
private String value;
private Node leftChild;
private Node rightChild;
....
我是新来的递归，所以没有任何的代码，我可以学习？ 谢谢！
Answer 1:
尝试
class Node {
private String value;
private Node left;
private Node right;
public Node(String value, Node left, Node right) {
this.value = value;
...
}
Node copy() {
Node left = null;
Node right = null;
if (this.left != null) {
left = this.left.copy();
}
if (this.right != null) {
right = this.right.copy();
}
return new Node(value, left, right);
}
}
Answer 2:
您可以使用这样的事情。 它会虽然老树深度第一明智和创建它的一个副本。
private Tree getCopyOfTree(oldTree) {
Tree newTree = new Tree();
newTree.setRootNode(new Node());
copy(oldTree.getRootNode(), newTree.getRootNode())
return newTree;
}
private void copy(Node oldNode, Node newNode) {
if (oldNode.getLeftChild != null) {
newNode.setLeftChild(new Node(oldNode.getLeftChild()));
copy(oldNode.getLeftChild, newNode.getLeftChild());
}
if (oldNode.getRightChild != null) {
newNode.setRightChild(new Node(oldNode.getRightChild()));
copy(oldNode.getRightChild, newNode.getRightChild());
}
}
Answer 3:
我喜欢叶夫根尼·Dorofeev的回答以上，但有时你可能无法将方法添加到类型Node ，你可能不会拥有它。 在这种情况下（这是在C＃）：
public static TreeNode CopyTree(TreeNode originalTreeNode)
{
if (originalTreeNode == null)
{
return null;
}
// copy current node's data
var copiedNode = new TreeNode(originalTreeNode.Data);
// copy current node's children
foreach (var childNode in originalTreeNode.Children)
{
copiedNode.Children.Add(CopyTree(childNode));
}
return copiedNode;
}
Answer 4:
这样做递归使用前序遍历。
public static Node CopyTheTree(Node root)
{
if (root == null)
{
return null;
}
Node newNode = new Node(null, null, root.Value);
newNode.Left= CopyTheTree(root.Left);
newNode.Right= CopyTheTree(root.Right);
return newNode;
}
Answer 5:
不知道，但尝试用你的树的后序遍历，并为您创造遍历每个节点的新节点的东西。 您可能需要堆栈用于存储您创建，使左，右子链接的节点。
Answer 6:
public static TreeNode copy( TreeNode source )
{
if( source == null )
return null;
else
return new TreeNode( source.getInfo( ), copy( source.getLeft( ) ), copy( source.getRight( ) ) );
}
/ 当然。 抱歉耽搁了。 反正......任何递归方法有一个基本情况，以及一个或多个递归的情况。 在这种情况下，第一行是显而易见的......如果参数的参数“来源”为空（因为它最终计算结果为，以结束该方法的操作），它会返回null; 如果没有，递归情况下被启动。 在这种情况下，你一旦递归完成返回复制的整个树。 “新”运算符使用，表明与遍历期间每次访问该树的各个节点树节点的实例，通过递归调用“复制”，其参数成为左右TreeNodes，则引用发生（如果有话）。 一旦源成为每个参数为空，则基础案例被启动时，释放所述递归堆栈返回到原始呼叫到“复制”，这是原始树的根的副本。 /
文章来源: How to deep copy a Binary Tree?
