Рекурсивное заполнение перетекает

Question

Искал на вопросе SO, где я предложил заполнение сетки узлов рекурсивны, и я думал, что я должен попробовать код для себя следующее держит перелив

public class Node { 

private Node left; 
private Node right; 
private Node up; 
private Node down; 
private int x; 
private int y; 

public Node(int x, int y) { 
    this.x = x; 
    this.y = y; 
} 

public static void buildGrid(Node node) { 
    fill(node); 
} 

private static void fill(Node node) { 
    fillLeft(node); 
    fillRight(node); 
} 

private static void fillRight(Node node) { 
    if (node.right != null || node.x > 10) 
     return; 

    node.right = new Node(node.x + 1, node.y); 
    fill(node.right); 
} 

private static void fillLeft(Node node) { 
    if (node.left != null || node.x <= 0) 
     return; 

    node.left = new Node(node.x - 1, node.y); 
    fill(node.left); 
} 

public static void main(String[] args) { 
    Node node = new Node(5, 5); 
    buildGrid(node); 
} 

Это так поздно я мог бы пропустил очень очевидное, но почему это переполнение? В первый раз fillLeft возвращается с fill(node.left), второй звонок fillLeft(node.left) должен немедленно возвращаться с node.left.right != null. То же самое для fillRight, не может понять, что здесь не так.

StackTrace

Exception in thread "main" java.lang.StackOverflowError 
at Node.<init>(Node.java:16) 
at Node.fillLeft(Node.java:42) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 
at Node.fill(Node.java:26) 
at Node.fillRight(Node.java:35) 
at Node.fill(Node.java:27) 
at Node.fillLeft(Node.java:43) 

Answer 1

Ваша проблема заключается в том, что вы не правильно создавать связи между новыми узлами. Вы хотите:

private static void fillRight(Node node) { 
    if (node.right != null || node.x > 10) 
     return; 

    node.right = new Node(node.x + 1, node.y); 
    node.right.left = node; // CURRENT NODE IS LEFT OF NEW NODE! 
    fill(node.right); 
} 

private static void fillLeft(Node node) { 
    if (node.left != null || node.x <= 0) 
     return; 

    node.left = new Node(node.x - 1, node.y); 
    node.left.right = node; // CURRENT NODE IS RIGHT OF NEW NODE! 
    fill(node.left); 
} 

Если распечатать координаты текущего узла заполнения вы можете увидеть это уходит влево и колеблется, так как ссылка «назад» всегда null. Добавьте это к началу fill(), чтобы увидеть, что происходит:

private static void fill(Node node) { 
    System.out.println("filling node " + node.x + " " + node.y + 
         " " + node.left + " " + node.right); 
    ... 

Во-вторых: Рекурсивный заполнение сетки становится грязным быстро и легко может привести к высокой рекурсивной глубины и быстрого перелива. С этими типами вещей вам лучше использовать очередь, чем делать это рекурсивно.

Answer 2

Позвоните fillRight() из fillRight() и аналогичным образом для левого.

В настоящее время это делает новый узел, затем вызывая fill() на этом узле, который имеет нулевые левые/правые указатели ...

Answer 3

Ваш fillLeft и fillRight никогда не ударят условия node.left! = Нуль и node.right! = null, который остановил бы рекурсию.

Похоже, что x и y являются вашими ключами, и вам придется хранить их на основе x и y где-то и возвращать их обратно, если они уже созданы, а не всегда называть новый узел.