Binärer Baum, der Nullen für Knoten zurückgibt

Question

Ich versuche einen binären Baum rekursiv für eine KI zu erstellen, die ich entwickle. Ich versuche, einen Baum zu bauen, aber alles kommt Null zurück. Die Sprache ist Java und ich benutze Eclipse. Außerdem bin ich auf einem Mac, wenn das irgendwas bedeutet. Der Baum sollte als Binärbaum mit instanziierten Knoten ohne Inhalt zurückgegeben werden.

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

ROOT classs

package FLINCH; 

public class Root extends Node { 

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

NODE CLASS

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

} 

OUTPUT

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) 

Ich hoffe, das hilft ...

Answer 1

Ich habe ein Stück Code, die Sie für 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

, wenn Sie Ihre buildRecursion rufen mit ctr = 1 verwenden können, werden Sie wahrscheinlich meinen Sie mit nur einen Baum bauen wollen eine zusätzliche Ebene und von Ihrem Kommentar, wo Sie einen Blattknoten erstellen möchten, muss die Bedingung geändert werden. in Ihrem Fall soll der Zustand sein:

if (ctr == 1) 

Ich habe einige Änderungen an der Funktion für eine bessere Leistung:

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

    } 

über das Problem bezüglich ich versuche, einen Baum zu bauen, aber alles kommt zurück null , in Ihrem outputTree und outputRecursion drucken Sie nichts anstelle von "-----", "LHS", "RHS" und wenn Sie erreichen, wo es keinen linken oder rechten Knoten gibt, drucken Sie "LHS/RHS ist Null", aber Sie sollten das mit einem wissen Blattknoten Dies ist ein akzeptiertes Verhalten. Wenn Sie also die Blattknoten erreichen, sollten Sie stattdessen ihre Werte drucken. Jedoch Sie die outputTreeRecursive wie folgt ändern können:

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

jetzt wahrscheinlich bekommen Sie eine bessere Vorstellung von Ihrem Baum