Двоичное дерево, возвращающее нули для узлов

Question

Я пытаюсь построить двоичное дерево рекурсивно для ИИ, который я разрабатываю. Я пытаюсь построить дерево, но все возвращается null. Язык Java, и я использую Eclipse. Кроме того, я нахожусь на Mac, если это что-то значит. Дерево должно быть возвращено как двоичное дерево с созданными узлами, но без какого-либо контента.

public class DecisionTree { 

     //build a generic, empty, tree 
     //building binary 

     Root r = new Root(); 

     public void build() //ok 
     { 

      Node lhs = new Node(); 
      Node rhs = new Node(); 
      lhs = new Node(); 
      rhs = new Node(); 

      r.lhs = lhs; 
      r.rhs = rhs; 
      lhs.parent = r; 
      rhs.parent = r; 

      builtRecursion(lhs, 1); 
      builtRecursion(rhs, 1); 

      outputTree(); 
      int ctr = 1; //levels of tree   
     } 

     public int builtRecursion(Node n, int ctr) 
     { 
      Node lhs = new Node(); 
      Node rhs = new Node(); 
      ctr++; 
      System.out.println("built recursion ctr is " + ctr); 
      if (ctr > 10) 
      { 
       //leaf node 
       Behaviors behavior = new Behaviors(); 
       Node node = behavior; 
       n.b = behavior; 
       return 0; 
      } 

      n.lhs = lhs; 
      n.rhs = rhs; 
      lhs.parent = n; 
      rhs.parent = n; 

      builtRecursion(lhs, ctr); 
      builtRecursion(rhs, ctr); 

      return ctr;   
     } 

     public void outputTree() 
     { 
      if (r != null) 
      { 
       System.out.println("Root"); 
      } 
      outputTreeRecursive(r); 
     } 

     public void outputTreeRecursive(Node n) 
     { 
      if (n.lhs != null) 
      { 
       System.out.println("------------------"); 
       System.out.println("LHS"); 
       outputTreeRecursive(n.lhs); 
      } 
      else { System.out.println("LHS is null");} 

      if (n.rhs != null) 
      { 
       System.out.println("-----------------"); 
       System.out.println("RHS"); 
       outputTreeRecursive(n.rhs); 
      } 
      else { System.out.println("RHS is null");} 

      System.out.println("-----------------"); 
     } 
} 

КОРНЕВАЯ CLASSS

package FLINCH; 

public class Root extends Node { 

    Node lhs = new Node(); 
    Node rhs = new Node(); 
} 

УЗЕЛ КЛАСС

package FLINCH; 

import java.util.ArrayList; 
import java.util.LinkedList; 

public class Node { 

    Node lhs = null; 
    Node rhs = null; 
    Node parent = null; 

    Decider d = new Decider(this); 
    Behaviors b = null; 

    public LinkedList getSuccessors() 
    { 
      LinkedList list = new LinkedList(); 

      list.add(lhs); 
      list.add(rhs); 
      return list; 
    } 

} 

ВЫХОД

GetAction Running 
Iterating through open list 
Size of open list is 1 
Peeked openLIst size is 1 
Peeking throguh open list 
Popping Open List 
LHS is null 
RHS is null 
Number of children is 2 
Children equals 2 
Decider childrens loop 
Child node is null 
Iterating through children 
Exception in thread "main" java.lang.NullPointerException 
    at FLINCH.A_Star_Search.search3(A_Star_Search.java:81) 
    at FLINCH.Soldier.search_behavior(Soldier.java:28) 
    at FLINCH.Main.getAction(Main.java:54) 
    at tests.GameVisualSimulationTest.main(GameVisualSimulationTest.java:52) 

Я надеюсь, что это помогает ...

Answer 1

У меня есть кусок кода, который вы можете использовать для BinaryTree

public class BinarySearchTree { 
public static Node root; 

public BinarySearchTree(){ 
    this.root = null; 
} 


public void insert(int id){ 
    Node newNode = new Node(id); 
    if(root==null){ 
     root = newNode; 
     return; 
    } 
    Node current = root; 
    Node parent = null; 
    while(true){ 
     parent = current; 
     if(id < current.data){    
      current = current.left; 
      if(current==null){ 
       parent.left = newNode; 
       return; 
      } 
     }else{ 
      current = current.right; 
      if(current==null){ 
       parent.right = newNode; 
       return; 
      } 
     } 
    } 
} 

public boolean find(int id){ 
    Node current = root; 
    while(current!=null){ 
     if(current.data==id){ 
      return true; 
     }else if(current.data > id){ 
      current = current.left; 
     }else{ 
      current = current.right; 
     } 
    } 
    return false; 
} 

public boolean delete(int id){ 
    Node parent = root; 
    Node current = root; 
    boolean isLeftChild = false; 
    while(current.data!=id){ 
     parent = current; 
     if(current.data > id){ 
      isLeftChild = true; 
      current = current.left; 
     }else{ 
      isLeftChild = false; 
      current = current.right; 
     } 
     if(current ==null){ 
      return false; 
     } 
    } 
    //if i am here that means we have found the node 
    //Case 1: if node to be deleted has no children 
    if(current.left==null && current.right==null){ 
     if(current==root){ 
      root = null; 
     } 
     if(isLeftChild ==true){ 
      parent.left = null; 
     }else{ 
      parent.right = null; 
     } 
    } 
    //Case 2 : if node to be deleted has only one child 
    else if(current.right==null){ 
     if(current==root){ 
      root = current.left; 
     }else if(isLeftChild){ 
      parent.left = current.left; 
     }else{ 
      parent.right = current.left; 
     } 
    } 
    else if(current.left==null){ 
     if(current==root){ 
      root = current.right; 
     }else if(isLeftChild){ 
      parent.left = current.right; 
     }else{ 
      parent.right = current.right; 
     } 
    }else if(current.left!=null && current.right!=null){ 

     //now we have found the minimum element in the right sub tree 
     Node successor = getSuccessor(current); 
     if(current==root){ 
      root = successor; 
     }else if(isLeftChild){ 
      parent.left = successor; 
     }else{ 
      parent.right = successor; 
     }   
     successor.left = current.left; 
    }  
    return true;   
} 

public Node getSuccessor(Node deleleNode){ 
    Node successsor =null; 
    Node successsorParent =null; 
    Node current = deleleNode.right; 
    while(current!=null){ 
     successsorParent = successsor; 
     successsor = current; 
     current = current.left; 
    } 
    //check if successor has the right child, it cannot have left child for sure 
    // if it does have the right child, add it to the left of  successorParent. 
    //  successsorParent 
    if(successsor!=deleleNode.right){ 
     successsorParent.left = successsor.right; 
     successsor.right = deleleNode.right; 
    } 
    return successsor; 
} 

public void display(Node root){ 
    if(root!=null){ 
     display(root.left); 
     System.out.print(" " + root.data); 
     display(root.right); 
    } 
} 


public static void printInOrder(Node root){ 

    if(root == null){ 
     return; 
    } 

    printInOrder(root.left); 
    System.out.print(root.data+" "); 
    printInOrder(root.right); 
} 

public static void printPreOrder(Node root){ 

    if(root == null){ 
     return; 
    } 
    System.out.print(root.data+" "); 
    printPreOrder(root.left); 

    printPreOrder(root.right); 
} 

public static void printPostOrder(Node root){ 

    if(root == null){ 
     return; 
    } 

    printPostOrder(root.left); 

    printPostOrder(root.right); 
    System.out.print(root.data+" "); 
} 


public static void main(String arg[]){ 
    BinarySearchTree b = new BinarySearchTree(); 
    b.insert(3);b.insert(8); 
    b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9); 
    b.insert(20);b.insert(25);b.insert(15);b.insert(16); 
    System.out.println("Original Tree : "); 
    b.display(b.root);  
    System.out.println(""); 
    System.out.println("Check whether Node with value 4 exists : " + b.find(4)); 
    System.out.println("Delete Node with no children (2) : " + b.delete(2));   
    b.display(root); 
    System.out.println("\n Delete Node with one child (4) : " + b.delete(4));  
    b.display(root); 
    System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));  
    b.display(root); 

    System.out.println(); 
    System.out.println("********* Printing In Order *********"); 
    printInOrder(root); 

    System.out.println(); 
    System.out.println("********* Printing Pre Order *********"); 
    printPreOrder(root); 

    System.out.println(); 
    System.out.println("********* Printing Post Order *********"); 
    printPostOrder(root); 
} 
} 

class Node{ 
    int data; 
    Node left; 
    Node right; 
    public Node(int data){ 
     this.data = data; 
     left = null; 
     right = null; 
    } 
} 

Answer 2

при вызове buildRecursion с ctr = 1, вы, вероятно, означает, что вы хотите построить дерево с только один дополнительный уровень и из вашего комментария, где вы планируете создавать листовой узел, необходимо изменить его состояние. в вашем случае условие должно быть:

if (ctr == 1) 

Я сделал некоторые изменения в функции для лучшего выхода:

public void builtRecursion(Node n, int ctr) 
    { 

     System.out.println("built recursion ctr is " + ctr); 
     if (ctr == 1) 
     { 
      //leaf node 
      Behaviors behavior = new Behaviors(); 
      n.b = behavior; 
      return; 
     } 

     Node lhs = new Node(); 
     Node rhs = new Node(); 

     n.lhs = lhs; 
     n.rhs = rhs; 
     lhs.parent = n; 
     rhs.parent = n; 


     builtRecursion(lhs, ctr--); 
     builtRecursion(rhs, ctr--); 

    } 

О проблеме относительно Я пытаюсь построить дерево, но все возвращается нуль , ну в ваших outputTree и outputRecursion вы ничего не печатаете, а не "-----", "LHS", "RHS", и в случае, если вы дойдете до левого или правого узла, вы напечатаете «LHS/RHS равно null», но вы должны знать, что с листовой узел это принятое поведение, поэтому, когда вы достигаете листовых узлов, вы должны печатать свои значения. Однако вы можете изменить outputTreeRecursive на следующее:

public void outputTreeRecursive(Node n) 
    { 
     if (n.lhs != null) 
     { 
      System.out.println("------------------"); 
      System.out.println("LHS"); 
      outputTreeRecursive(n.lhs); 
     } 
     else { 
       System.out.println("LHS is null"); 
       if(n.b != null) 
        System.out.println("Leaf node"); 
      } 

     if (n.rhs != null) 
     { 
      System.out.println("-----------------"); 
      System.out.println("RHS"); 
      outputTreeRecursive(n.rhs); 
     } 
     else { 
       System.out.println("RHS is null"); 
       if(n.b != null) 
        System.out.println("Leaf node");     
      } 

     System.out.println("-----------------"); 
    } 

теперь, вероятно, вы получите более полное представление о дереве