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

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

这是我的主类，用我想要的 vector 运行它:

public class TryTree{

public static void main(String[] args) {

    byte vectorPosibles[]={-1,-1};
    SolutionTree tree=new SolutionTree(vectorPosibles); //tree of posible solutions and it need to pass a vector [-1,-1]

  }
}

它不会生成我需要的所有节点。查看包含所有节点的图像: Image with nodes what i need, 整数我需要递归地执行此操作，而不是使用扫描。

Answer 1

为此，您需要在构造函数 TreeNode 中使用它: System.arraycopy( vector Posible, 0, this. vector Posible, 0, vector Posible.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)，因为如果您声明一个，它将被同一个 vector 引用。那么代码将如下所示:

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;
  }
 }
}