如何创建递归方法来生成二叉树？

Question

当右侧的递归迭代到达状态 2 并返回时，问题就出现了，因为父亲取了一个不应该取的值。

这是我的节点创建者类，它有右侧和左侧：

public class TreeNodo{

    public byte vectorPosible[]; 

    public int stage; //my stages and index posision of array

    public TreeNodo right; // if goes to right mean 1, in index posision of array

    public TreeNodo left; // if goes to right mean 0, in the index posision of array

    //contructor

    public TreeNodo(byte vectorPosible[], int currentStage){

        this.vectorPosible=vectorPosible;

        this.stage=currentStage; 

        this.right=null;

        this.left=null;

    }

这是我的递归类，我初始化构造函数，此时我开始递归：

public class SolutionTree{

TreeNodo root; //it saves the vector [-1,-1] that its initial stage

//contructor 

public SolutionTree(byte vectorPosible[], int currentStage){

    this.root=new TreeNodo(vectorPosible, currentStage);

    this.generarTreePSR(root, vectorPosible, vectorPosible.length, currentStage+1); //Generate a Tree of Possible Solutions Recursively

}

//Metod to insert Tree Node Recursively

public static void generarTreePSR(TreeNode father,byte vectorPosible[],int maxStage, int currentStage){  //in this case maxStage is 2

    TreeNode newNode= new TreeNode(vectorPosible, currentStage);

    System.out.println("newNode.left: "+(newNode.left==null));

    System.out.println("newNode.right: "+(newNode.right==null));

    System.out.println();       

    System.out.println("newNode stage: "+newNode.stage);

    if(newNode.stage==maxStage){ //BASE CASE, IF STAGE == 2

        System.out.println("Reached this stage max: "+newNode.stage);

        System.out.println("I return");

        return;

    }else{ // it isn't in the base case, so tree follow growing

        System.out.print("Look i'm father and i'm before of left, my vector is: ");

        for (int j=0;j<father.vectorPosible.length;j++) { //i show the father vector's

            System.out.print(father.vectorPosible[j]);

            System.out.print(" ");

        }

它不会生成我需要的所有节点。查看包含所有节点的图像： 包含我需要的节点的图像 ，int 我需要递归执行而不是扫描。

Answer 1

为此，您需要在 TreeNode 的构造函数中使用它： System.arraycopy(vectorPosible, 0, this.vectorPosible, 0, vectorPosible.length);那么代码将如下所示：&nbsp;public class TreeNodo{&nbsp; &nbsp; public byte vectorPosible[];&nbsp;&nbsp; &nbsp; public int stage; //my stages and index posision of array&nbsp; &nbsp; public TreeNodo right; // if goes to right mean 1, in index posision of array&nbsp; &nbsp; public TreeNodo left; // if goes to right mean 0, in the index posision of array&nbsp; &nbsp; //contructor&nbsp; &nbsp; public TreeNodo(byte vectorPosible[], int currentStage){&nbsp; &nbsp; &nbsp; this.vectorPosible=vectorPosible;&nbsp; &nbsp; &nbsp; this.stage=currentStage;&nbsp;&nbsp; &nbsp; &nbsp; this.right=null;&nbsp; &nbsp; &nbsp; this.left=null;&nbsp; }}除此之外，您还必须在SolutionTree中声明两个newNode（1和2），因为如果您声明一个，它将被相同的向量引用。那么代码将如下所示：public class SolutionTree{&nbsp; TreeNodo root; //it saves the vector [-1,-1] that its initial stage&nbsp; //contructor&nbsp;&nbsp; public SolutionTree(byte vectorPosible[], int currentStage){&nbsp; &nbsp; &nbsp; this.root=new TreeNodo(vectorPosible, currentStage);&nbsp; &nbsp; &nbsp; this.generarTreePSR(root, vectorPosible, vectorPosible.length, currentStage+1); //Generate a Tree of Possible Solutions Recursively&nbsp; }&nbsp; //Metod to insert Tree Node Recursively&nbsp; public static void generarTreePSR(TreeNode father,byte vectorPosible[],int maxStage, int currentStage){&nbsp; //in this case maxStage is 2&nbsp; &nbsp; if(currentStage==maxStage){ //BASE CASE, IF STAGE == 2&nbsp; &nbsp; &nbsp; System.out.println("Reached this stage max: "+currentStage);&nbsp; &nbsp; &nbsp; System.out.println("I return");&nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }else{ // it isn't in the base case, so tree follow growing&nbsp; &nbsp; &nbsp; //NEW TREE NODE1&nbsp; &nbsp; &nbsp; &nbsp; TreeNode newNode1=new TreeNode(father.getVectorPos(), currentStage); //<------Solucion&nbsp; &nbsp; &nbsp; &nbsp; newNode1.stage=currentStage;&nbsp; &nbsp; &nbsp; //NEW TREE NODE2&nbsp; &nbsp; &nbsp; &nbsp; TreeNode newNode2= new TreeNode(father.getVectorPos(), currentStage); //<------Solucion&nbsp; &nbsp; &nbsp; &nbsp; newNode2.stage=currentStage;&nbsp; &nbsp; &nbsp; System.out.print("Look i'm father and i'm before of left, my vector is: ");&nbsp; &nbsp; &nbsp; for (int j=0;j<father.vectorPosible.length;j++) { //i show the father vector's&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(father.vectorPosible[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(" ");&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; System.out.println("I'm before if Left, and it is: "+(father.left==null));&nbsp; &nbsp; &nbsp; if(father.left==null){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.vectorPosible[newNode.stage]=0; //insert 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; father.left=newNode; //asign node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j=0;j<father.left.vectorPosible.length;j++) { //i show what i insert into this left node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(father.left.vectorPosible[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(" ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Nodo added left with success");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; generarTreePSR(father.left, father.left.vectorPosible, maxStage, currentStage+1);&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; System.out.print("Look i'm father and i'm before of right, my vector is: ");&nbsp; &nbsp; &nbsp; for (int j=0;j<father.vectorPosible.length;j++) { //i show the father vector's&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(father.vectorPosible[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(" ");&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; System.out.println("I'm before if Right, and it is: "+(father.right==null));&nbsp; &nbsp; &nbsp; if(father.right==null){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.vectorPosible[newNode.stage]=1; //insert 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; father.right=newNode; //asign node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j=0;j<father.right.vectorPosible.length;j++) {&nbsp; //i show what i insert into this right node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(father.right.vectorPosible[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(" ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Nodo added right with success");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; generarTreePSR(father.right, father.right.vectorPosible, maxStage, currentStage+1);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return;&nbsp; }&nbsp;}}