Зеркальное отображение бинарного дерева

Question

У меня есть простой класс Node для построения узла дерева в моем двоичном дереве:

class Node {
    int data;
    Node left;
    Node right;

    public Node(int i) {
        this.data = i;
    }
}

Я написал простой класс Tree, который будет использовать структуру Node для построения дерева:

class Tree {
    Node root;
}

Я пытаюсь написать рекурсивную функцию mirror () в моем классе Tree, которая будет возвращать зеркальную версию дерева (левый и правый узлы поменялись местами).

Так что, если я вызову эту функцию для Tree t, я бы ожидал начать с корня и поменять местами все узлы, пока мы не достигнем узла, у которого больше нет дочерних мест для обмена. Часть, с которой я борюсь, - это после того, как мы поменяли местами дочерние узлы, как я могу рекурсивно вызвать функцию зеркала на этих узлах, а затем вернуть зеркальное дерево.

Как видите, приведенный ниже код поменяет местами дочерние узлы корневого узла, но после этого я застрял, поскольку не могу вызвать функцию зеркального отображения на узлах, а только на дереве.

public Tree mirror() {
    Node temp = this.root.left;
    this.root.left = this.root.right;
    this.root.right = temp;

Если бы вы могли указать мне правильное направление, я был бы признателен.

Answer 1

Вам нужен отдельный метод, который будет принимать Node объект, зеркально отражать его дочерние элементы и вызывать себя рекурсивно.

public Tree mirror() {
    mirrorInternal(this.root);
    return this;
}

private void mirrorInternal(Node node) {
    Node tmp = node.left;
    node.left = node.right;
    node.right = tmp;
    if (node.left != null) {
        mirrorInternal(node.left);
    }
    if (node.right != null) {
        mirrorInternal(node.right);
    }
}      

Answer 2

void mirror (Tree tree) {
  mirror (tree.root);
}

Node mirror (Node node) {
  if (node != null) {
    Node temp = node.left;
    node.left = mirror (node.right);
    node.right = mirror (temp);
  }
  return node;
}

Answer 3

Полагаю, вы также можете изменить класс Node таким образом, чтобы он использовал флаг для зеркального поведения:

class Node {
    int data;
    Node[] children;

    public Node(int i) {
        this.data = i;
        this.children = new Node[2];
    }

    public void setLeft(Node node) {
        children[0] = node;
    }

    public void setRight(Node node) {
        children[1] = node;
    }

    public Node getLeft(boolean mirrored) {
        return mirrored ? children[1] : children[0];
    }

    public Node getRight(boolean mirrored) {
        return mirrored ? children[0] : children[1];
    }
}