package com.binarytree;
public interface Node {
int getMaxLeafDepth();
void addValue(int value);
String toString();
}Вот пример кода класса, в котором используется рекурсия.
package com.binarytree.procedure;
import com.binarytree.Node;
public class ProcedureRecursionTree implements Node {
private NodeElement root;
public ProcedureRecursionTree(int rootValue) {
root = new NodeElement(rootValue);
}
@Override
public void addValue(int newValue) {
addValue(root, newValue);
}
private void addValue(NodeElement node, int newValue) {
if (newValue < node.value) {
node.left = addTo(node.left, newValue);
} else if (node.value < newValue) {
node.right = addTo(node.right, newValue);
}
}
private NodeElement addTo(NodeElement node, int newValue) {
if (node != null) {
addValue(node, newValue);
return node;
} else {
return new NodeElement(newValue);
}
}
@Override
public int getMaxLeafDepth() {
return getMaxLeafDepthFrom(0, root);
}
private int getMaxLeafDepthFrom(int depth, NodeElement node) {
if (node == null) {
return depth;
}
return 1 + Math.max(getMaxLeafDepthFrom(depth, node.left),
getMaxLeafDepthFrom(depth, node.right));
}
@Override
public String toString() {
return toString(root);
}
private String toStringSubnode(NodeElement node) {
if (node != null) {
return toString(node);
}
return null;
}
private String toString(NodeElement node) {
return String.format("(%s, %s, %s)",
node.value,
toStringSubnode(node.left),
toStringSubnode(node.right));
}
}
Это класс, в котором хранятся данные
package com.binarytree.procedure;
public class NodeElement {
int value;
int parentNodeValue;
NodeElement left;
NodeElement right;
public NodeElement(int value) {
this.value = value;
}
}Ну и? Все нормально на первый взгляд. Методы маленькие, дублирования нет, все вполне читабельно. Да, но тут код пахнет другим - класс ProcedureRecursionTree инкапсулируя NodeElement root рекурсивно проходится по всем дочерним узлам/листьям root ноды. Это удобно - все ноды одного типа. Но это не по OOP. Правило простое.
Метод объекта должен работать только с полями своего объекта, иначе метод должен быть перемещен в тот объект, чьи данные использует интенсивнее всего. Если же данные не возможно расширить новым методом, тогда создается новый класс, их инкапсулирующий (или наследующий - что применимее), с последующим переносом в него исходного метода.
Вот этой задачкой я и предлагаю заняться. Рефакторинг, как оказалось недавно, в более широком виде, Фаулеровский и называется "Преобразования процедурного проекта в объекты (Convert Procedural Design to Objects)", я же его раньше называл "замена рекурсии делегированием".
Вывод пока напрашивается громкий - там где OOP там не должно быть рекурсии с передачей данных.
Вот кстати тест:
package com.binarytree;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
import com.binarytree.Node;
public class TreeTest {
Node createNode(int rootValue) {
return new ProcedureRecursionTree(rootValue);
}
@Test
public void testAddLeftToRoot() {
Node node = createNode(5);
node.addValue(4);
assertEquals("(5, (4, null, null), null)", node.toString());
}
@Test
public void testAddRightToRoot() {
Node node = createNode(5);
node.addValue(6);
node.addValue(4);
assertEquals("(5, (4, null, null), (6, null, null))", node.toString());
}
@Test
public void testStartSecondLevel() {
Node node = createNode(5);
node.addValue(6);
node.addValue(12);
node.addValue(3);
assertEquals("(5, (3, null, null), " +
"(6, null, (12, null, null)))", node.toString());
}
@Test
public void testGetDepthFrom3LevelOnlyRightTree() {
Node node = createNode(5);
node.addValue(6);
node.addValue(12);
assertEquals(3, node.getMaxLeafDepth());
assertEquals("(5, null, (6, null, (12, null, null)))",
node.toString());
}
@Test
public void testGetDepthFrom3LevelLeftRightTree() {
Node node = createNode(5);
node.addValue(1);
node.addValue(2);
assertEquals(3, node.getMaxLeafDepth());
assertEquals("(5, (1, null, (2, null, null)), null)",
node.toString());
}
@Test
public void testGetDepthFrom4LevelleftRightTree() {
Node node = createNode(5);
node.addValue(6);
node.addValue(12);
node.addValue(16);
node.addValue(3);
node.addValue(1);
node.addValue(0);
assertEquals(4, node.getMaxLeafDepth());
assertEquals("(5, (3, (1, (0, null, null), null), null), " +
"(6, null, (12, null, (16, null, null))))",
node.toString());
}
@Test
public void testGetDepthFrom5LevelTree() {
Node node = createNode(5);
node.addValue(4);
node.addValue(6);
node.addValue(3);
node.addValue(7);
node.addValue(2);
node.addValue(8);
node.addValue(1);
node.addValue(9);
assertEquals(5, node.getMaxLeafDepth());
assertEquals("(5, (4, (3, (2, (1, null, null), null), null), null), " +
"(6, null, (7, null, (8, null, (9, null, null)))))",
node.toString());
}
}
Приятного аппетита. Продолжение следует.
Сообщения
