правильный способ клонирования дерева

пытаюсь понять, как работает клон с деревом, поэтому я хотел сделать дерево, которое на входе и выходе будет одним и тем же деревом (то есть одинаковые значения в узлах, узлы соединены одинаково), но он должен состоять из разных объектов, так как я понимаю концепцию клонирования, которую я пытался сделать, вот мой код для лучшего понимания;

class Node {
    public int val;
    int key;
    Node left, right;

    public Node(int data){
        key = data;
        left = right = null;
    }
}
class binaryTree {

    Node root;

    binaryTree() {
        root = null;
    }


    void preOrder(Node node) {
        if (node == null)
            return;

        System.out.print(node.key + " ");

        preOrder(node.left);

        preOrder(node.right);
    }

    void preOrder_traversal() {
        preOrder(root);
    }


        public Node cloneTree(Node root) {
            if (root == null) return null;
            Node newNode = new Node(root.val);
            newNode.left = cloneTree(root.left);
            newNode.right = cloneTree(root.right);

            return newNode;

        }
    }

это основной класс

public class Main {

    public static void main(String[] args) {
        binaryTree tree = new binaryTree();
        /*        45
                //  \\
                10   90
               // \\
               7   12      */
        tree.root = new Node(45);
        tree.root.left = new Node(10);
        tree.root.right = new Node(90);
        tree.root.left.left = new Node(7);
        tree.root.left.right = new Node(12);
         //  Traversal
        System.out.println("        \t\t  45\n"   +
                "                //  \\\\\n" +
                "                10   90\n" +
                "               // \\\\\n" +
                "               7   12    :");

        System.out.print("  \t \t\t" );
        tree.preOrder_traversal();
        System.out.println();
       
        tree.cloneTree(tree.root);
        System.out.print("  \t \t\t" );
        tree.preOrder_traversal();

    }
}

выход

45 // \ 10 90 // \ 7 12 : 45 10 7 12 90 45 10 7 12 90

в функции cloneTree() я пытался создать новый объект из класса Node; это правильный способ сделать объект из дерева или это лучший способ


java clone tree
person abl    schedule 16.06.2021    source источник
comment
Отвечает ли это на ваш вопрос? Как глубоко скопировать двоичное дерево?   -  person Martin Niederl    schedule 16.06.2021

Ответы (1)


arrow_upward
0
arrow_downward

То, как вы это делаете, прекрасно (хотя я не заметил очевидной путаницы между key и val). Было бы еще лучше, если бы вы добавили перегрузку конструктора Node, которая принимает аргументы для left и right:

public Node(int data, Node left, Node right) {
    key = data;
    this.left = left;
    this.right = right;
}

Тогда метод cloneTree может быть:

public Node cloneTree(Node root) {
    return root == null ? null 
         : new Node(root.key, cloneTree(root.left), cloneTree(root.right));
}
person trincot    schedule 16.06.2021