爲節點返回空值的二叉樹

-1

我試圖爲我正在開發的AI遞歸地構建二叉樹。我嘗試構建一棵樹，但所有內容都返回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("-----------------"); 
     } 
}

ROOT班組長

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

}

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)

我希望這有助於...

來源

2016-04-13 Ted Gress

只有葉子左，右後代應打印成'null'。分享你的輸出，以及你如何定義'Node'和'Root'（我認爲'Root'擴展了'Node'，一個帶有3個變量的類 - 'lhs'，'rhs'和'parent'？） –

你的意思是「一切都回來了」？你的算法看起來很好，當我嘗試它時（深度小於10），輸出結果就是我所期望的。我建議你用10代替2或3來嘗試，然後發佈輸出並解釋輸出結果不是你所期望的。 – ajb

ajb：將二叉樹實例化到某個級別。當我嘗試遍歷它時，我從根開始，然後轉到左側和右側，但是這些值爲空，當它們應該是Node對象的實例等等，直到它到達樹葉。我試着用值2到10來得到相同的結果 –

我有一段代碼，當你與ctr = 1打電話給你buildRecursion，你可以使用二叉樹

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

來源

2016-04-13 06:00:51 KayV

，你可能說你想建立只是一個樹一個額外的級別，並從您的意見，你希望建立一個葉節點，該條件需要修改。你的情況的條件應該是：

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爲空」，但你應該知道葉節點這是一個可接受的行爲，所以當你到達葉節點時，你應該打印它們的值。但是你可以改變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("-----------------"); 
    }

現在大概你會得到更好的主意，關於你的樹

來源

2016-04-13 06:26:40 Pooya

爲節點返回空值的二叉樹

回答

相關問題