使用预先遍历在Java中复制二叉树

我试图使用预遍历复制二叉树，但我被卡住了。由于我不把任何值到一个新的树他们显然是不正确复制...使用预先遍历在Java中复制二叉树

public class Node{ 

int key; 
String name; 

Node leftChild; 
Node rightChild; 

Node(int key, String name){ 
    this.key = key; 
    this.name = name; 

} 



public class BinaryTree{ 

public Node root; 

public void copyTree(Node focusNode){ 

    if(focusNode != null){ 

     Node copyNode = new Node(focusNode.key, focusNode.name); 

     //System.out.println(copyNode); 

     copyTree(focusNode.leftChild); 
     copyTree(focusNode.rightChild); 
    } 
}

}

来源

2016-03-04 jlog

你做的事情对我来说看起来不错。那么问题究竟在哪里呢？ – pczeus

你的问题是什么？什么不按预期工作？根据你的'copyTree'方法，它看起来像你正在创建一个本地副本（在方法中），但由于副本只存在于方法中，所以它会超出范围（并且有资格进行垃圾回收） 'copyTree'方法返回。也许你想改变'copyTree'的签名来返回'copyNode'（而不是当前的'void'返回值），以便返回你正在构造的副本？ –

感谢您的回复，我实际上并没有将它们复制到新的“复制”树中，这正是我想要的，但您的回复仍然为我清除了一些内容。 – jlog

这里有一个解决方案。出于演示目的，我在Node类中添加了toString()方法。

class Node { 

    int key; 
    String name; 

    Node leftChild; 
    Node rightChild; 

    Node(int key, String name) { 
     this.key = key; 
     this.name = name; 
    } 

    public String toString() { 
     return "[" + key + "," + name + "]"; 
    } 
}

的BinaryTree被稍微修改，以及：

class BinaryTree { 

    public Node root; 

    public BinaryTree copyTree(Node focusNode) { 
     BinaryTree bt = new BinaryTree(); 
     bt.root = preOrderCopy(focusNode); 
     return bt; 
    } 

    public static void preOrderPrint(BinaryTree t) { 
     preOrderPrint(t.root); 
    } 

    public static void preOrderPrint(Node n) { 
     if (n == null) { 
      // base case 
      return; 
     } 
     System.out.println(n); 
     preOrderPrint(n.leftChild); 
     preOrderPrint(n.rightChild); 

    } 

    private Node preOrderCopy(Node focusNode) { 
     if (focusNode == null) { 
      // base case 
      return null; 
     } 
     Node copy = new Node(focusNode.key, focusNode.name); 
     copy.leftChild = preOrderCopy(focusNode.leftChild); 
     copy.rightChild = preOrderCopy(focusNode.rightChild); 
     return copy; 
    } 

}

要测试的代码，我基于关于Wikipedia page for Tree Traversal所示的一个创建的BinaryTree。下面是本例中使用的树的图片：

这个例子的正确预购遍历是：F, B, A, D, C, E, G, I, H。您可以使用下面的代码来测试这个实现：

public class NodeTest { 

    public static void main(String[] args) { 
     BinaryTree bt = new BinaryTree(); 
     Node a = new Node(1, "A"); 
     Node b = new Node(2, "B"); 
     Node c = new Node(3, "C"); 
     Node d = new Node(4, "D"); 
     Node e = new Node(5, "E"); 
     Node f = new Node(6, "F"); 
     Node g = new Node(7, "G"); 
     Node h = new Node(8, "H"); 
     Node i = new Node(9, "I"); 
     f.leftChild = b; 
     b.leftChild = a; 
     b.rightChild = d; 
     d.leftChild = c; 
     d.rightChild = e; 
     f.rightChild = g; 
     g.rightChild = i; 
     i.leftChild = h; 
     bt.root = f; 

     System.out.println("Print full tree:"); 
     BinaryTree.preOrderPrint(bt.copyTree(f)); 

     System.out.println("Only print f's left sub-tree:"); 
     BinaryTree.preOrderPrint(bt.copyTree(f.leftChild)); 

    } 

}

运行上面的代码产生以下输出：

Print full tree: 
[6,F] 
[2,B] 
[1,A] 
[4,D] 
[3,C] 
[5,E] 
[7,G] 
[9,I] 
[8,H] 
Only print f's left sub-tree: 
[2,B] 
[1,A] 
[4,D] 
[3,C] 
[5,E]

来源

2016-03-04 03:18:30

从树复制到B树。你可以使用像我这样的两种静态方法。我的想法来自添加Element方法并删除Element方法。他们是相似的。

public static Node copyRec(Node a, Node b)//copy from b to a 
{ 
    if(b!=null) 
    { 
     a=new Node(b.data); 
     a.leftChild=copyRec(a.leftChild,b.leftChild); 
     a.rightChild=copyRec(a.rightChild,b.rightChild); 
     return a; 
    } 
    return null; 
} 
public static void copy(BST a, BST b) 
{ 
    a.root=copyRec(a.root,b.root); 
}

来源

2017-09-01 08:16:28

使用预先遍历在Java中复制二叉树

回答

相关问题