Копирование двоичного дерева в Java с использованием обхода предзаказов

Question

Я пытаюсь скопировать двоичное дерево, используя предварительный обход, но я застрял. Поскольку я не прикладывая ни одному из значений в новое дерево они, очевидно, не копируя правильно ...

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

}

Answer 1

Вот одно решение. Я добавил метод toString() для класса Node для целей презентации.

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 The был немного изменен, а также:

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

} 

Для проверки кода, я создал BinaryTree на основе изображенного на Wikipedia page for Tree Traversal. Вот картина дерева используется в этом примере:

Правильный обход Предзаказ для этого примера: 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] 

Answer 2

Чтобы скопировать из дерева а для дерева б. вы можете использовать два статических метода, подобных мне. Моя идея связана с добавлением метода 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); 
}