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

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 Recursivelypublic 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);

那么代码将如下所示：

 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;

  }

}

除此之外，您还必须在SolutionTree中声明两个newNode（1和2），因为如果您声明一个，它将被相同的向量引用。那么代码将如下所示：

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

    if(currentStage==maxStage){ //BASE CASE, IF STAGE == 2

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

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

      return;

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

      //NEW TREE NODE1

        TreeNode newNode1=new TreeNode(father.getVectorPos(), currentStage); //<------Solucion

        newNode1.stage=currentStage;

      //NEW TREE NODE2

        TreeNode newNode2= new TreeNode(father.getVectorPos(), currentStage); //<------Solucion

        newNode2.stage=currentStage;

      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(" ");

      }

      System.out.println();

      System.out.println("I'm before if Left, and it is: "+(father.left==null));

      if(father.left==null){

              newNode.vectorPosible[newNode.stage]=0; //insert 0

              father.left=newNode; //asign node

              for (int j=0;j<father.left.vectorPosible.length;j++) { //i show what i insert into this left node

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

                  System.out.print(" ");

              }

              System.out.println();

              System.out.println("Nodo added left with success");

              System.out.println();

              generarTreePSR(father.left, father.left.vectorPosible, maxStage, currentStage+1);

    }

      System.out.print("Look i'm father and i'm before of right, 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(" ");

      }

      System.out.println();

      System.out.println("I'm before if Right, and it is: "+(father.right==null));

      if(father.right==null){

              newNode.vectorPosible[newNode.stage]=1; //insert 1

              father.right=newNode; //asign node

              for (int j=0;j<father.right.vectorPosible.length;j++) {  //i show what i insert into this right node

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

                  System.out.print(" ");

              }

              System.out.println();

              System.out.println("Nodo added right with success");

              System.out.println();

              generarTreePSR(father.right, father.right.vectorPosible, maxStage, currentStage+1);

      }

      return;

  }

 }

}