Рекурсивная генерация дерева в Java - PullRequest
Новая
       24

Рекурсивная генерация дерева в Java

2 голосов
/ 14 ноября 2011

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

public class TreeTest
{   

    public static void main(String Args[])
    {   
        sBNode bTree;
        sWNode wTree;

        bTree = new sBNode();
        wTree = new sWNode();

        TreeTest ai = new TreeTest();       

        bTree.depth = 0;
        System.out.println(bTree.depth);
        ai.genB(bTree, 2);
        ai.printTree(bTree);    
    }

    public Treetest()
    {

    }

    public boolean leaf(sBNode node)
    {
        if(node.pe1==null && node.pe2==null && node.pe3==null && node.ee1==null && node.ee2==null && node.ee3==null)
            return true;
        else
            return false;
    }

    public void genB(sBNode parent, int ddepth)
    {
        int pdepth;

        if(parent.depth != ddepth)
        {           
            System.out.println(parent.depth);
            pdepth = parent.depth++;
            sBNode pe1 = new sBNode();
            sBNode pe2 = new sBNode();
            sBNode pe3 = new sBNode();  
            sBNode ee1 = new sBNode();
            sBNode ee2 = new sBNode();
            sBNode ee3 = new sBNode();

            pe1.depth = pdepth;
            pe2.depth = pdepth;
            pe3.depth = pdepth;
            ee1.depth = pdepth;
            ee2.depth = pdepth;
            ee3.depth = pdepth;
            pe1.parent = parent;
            pe2.parent = parent;
            pe3.parent = parent;
            ee1.parent = parent;
            ee2.parent = parent;
            ee3.parent = parent;

            genB(pe1, ddepth);
            //genB(pe2, ddepth);
            //genB(pe3, ddepth);
            //genB(ee1, ddepth);
            //genB(ee2, ddepth);
            //genB(ee3, ddepth);            
        }       
    }

    public void printTree(sBNode node)
    {
        while(!leaf(node))
        {
            System.out.println(node.depth);
            printTree(node.pe1);
            printTree(node.pe2);
            printTree(node.pe3);
            printTree(node.ee1);
            printTree(node.ee2);
            printTree(node.ee3);
        }
    }
}

final class sBNode
{   
    public String state = "BCXXXCXXX";

    //utility value
    public boolean war;
    public int score;
    public int oscore;
    public int utility;
    public int min;
    public int max;
    public int depth;

    sBNode pe1;
    sBNode pe2;
    sBNode pe3; 
    sBNode ee1;
    sBNode ee2;
    sBNode ee3;
    sBNode parent;

    public sBNode()
    {
        war = false;
        score = 0;
        oscore = 0;
        utility = 0;
        min = 0;
        max = 0;
        depth = 0;
    }
}

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

Ответы [ 2 ]

5 голосов
/ 14 ноября 2011

Обнаружил вашу проблему: 

pdepth = parent.depth++;

должно быть: 

pdepth = parent.depth + 1;

Вы выполняете постинкремент, что означает, что сначала выполняется присвоение, а затем приращение.Значение pdepth всегда равно нулю.

0 голосов
/ 14 ноября 2011

Преступник
pdepth = parent.depth ++;
line.

Вы используете оператор постинкрементного преобразования вместо оператора предварительного инкремента.Таким образом, parent.depth всегда 0 , что приводит к бесконечной рекурсии.

-JB-

...