Отразить бинарное дерево
У меня есть простой класс Node для построения узла дерева в моем двоичном дереве:
class Node {
int data;
Node left;
Node right;
public Node(int i) {
this.data = i;
}
}
Я написал простой класс Tree, который будет использовать структуру Node для построения дерева:
class Tree {
Node root;
}
Я пытаюсь написать рекурсивную функцию зеркало() в моем классе Tree, которая будет возвращать зеркальную версию дерева (левый и правый узлы поменялись местами).
Поэтому, если я вызову эту функцию для дерева t, я ожидаю начать с корня и поменять местами все узлы, пока мы не достигнем узла, у которого больше нет дочерних элементов для обмена. Часть, с которой я борюсь, заключается в том, что после того, как мы поменяли местами дочерние узлы корневых узлов, я могу рекурсивно вызвать функцию зеркала на этих узлах, а затем вернуть зеркальное дерево.
Как видите, приведенный ниже код поменяет местами дочерние элементы корневого узла, но после этого я застрял, так как не могу вызвать зеркальную функцию для узлов, только для дерева.
public Tree mirror() {
Node temp = this.root.left;
this.root.left = this.root.right;
this.root.right = temp;
Если бы вы могли указать мне в правильном направлении, я был бы признателен.
Вы должны заставить зеркальный метод принимать узел, а не все дерево. Таким образом, вы можете вызывать его рекурсивно для правого и левого элементов.
связанные: stackoverflow.com/questions/4366251/…
Подсказка: вы должны сделать это рекурсивным способом (передать узел в качестве параметра функции) или сделать это итеративно (используя стеки).
@ClaudiuGuja Я бы так и сделал, но что, если я хочу просто вызвать tree.mirror(), чтобы получить зеркальное дерево? Если он принимает узел, мне нужно вызвать зеркало (узел), что кажется утомительным, поскольку мне придется создать новый объект узла.
Ответы 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];
}
}
Вам нужен отдельный метод, который будет принимать 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);
}
}
Это имеет смысл. Будет ли это наиболее эффективным способом приблизиться к чему-то подобному? Нельзя ли это сделать одним методом?
@juyebgastro это самый простой способ. Поскольку это будет единственный метод, который должен принимать объекты разных типов, в этом случае может потребоваться дополнительное кодирование.
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;
}
Разве вы не можете просто пройти по дереву справа налево, а не слева направо? По тому же дереву вы можете пройти его ASC или DESC.