So geben Sie einen Binärbaum in Java ein

Question

Ich brauche Hilfe beim Implementieren eines Binärbaums in Java.

Ich meine nicht wie es aus einer Textdatei zu lesen. Ich meine, der Benutzer gibt den Baum mit einem Scanner ein und erstellt und gibt dann die Baumwerte aus. Ein "-" Zeichen bedeutet auch einen Nullwert im Baum.

Bisher habe ich eine Knoten-Klasse arbeiten, aber ich brauche es, um einen Baum aus den genannten Knoten zu machen. Es muss auch wissen, wann man keine Eingaben mehr akzeptiert.

Hier ist der Anfang meines Codes. Ich brauche einen Weg, um eine Liste von Knoten einzugeben und sie mit diesen Klassen zu einem Baum zu machen.

import java.util.Scanner; 
import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 
import java.util.Queue; 
import java.util.LinkedList; 


/** 
* 
* @author phirstprince 
*/ 

class TreeNode { 
    int data; 
    TreeNode LC, RC; 

    public TreeNode(int x) { 
     data = x; 
     LC = null; 
     RC = null; 
    } 

} 

    public class TreeDeserialize { 

     /** 
     * @param args the command line arguments 
     */ 
     public static void main(String[] args) { 
      Scanner input = new Scanner(System.in); 
      int x = input.nextInt(); 
     } 

    } 

Wie zum Beispiel, wenn eine Person eingegeben wurde diese (die - wobei null Knoten)

1 
2 
3 
- 
4 
5 
6 
- 
- 
- 
- 
- 
- 

Es es in einen Baum, wie dies organisieren würde.

  1 
    / \ 
     2  3 
     \ /\ 
     4 5 6 

Jeder denkt, dass sie helfen können? Ich glaube, es würde eine Warteschlange erfordern. Wie kann man sicherstellen, dass es weiß, wann man keine Eingaben mehr akzeptiert?

Answer 1

Sie sollten eine Methode entwickeln, die die Zahlen überprüft und sie zum Beispiel hinzufügt. Wenn die Zahl größer als der Elternwert ist, sollte sie rechts hinzugefügt werden, wenn sie kleiner ist als der Elternwert, sollte sie links hinzugefügt werden . Ich denke, Sie können diese Funktion mit Hilfe von Rekursion entwickeln.

Answer 2

Hier ist eine Funktion, die versucht, den neuen Knoten levelweise von links nach rechts einzufügen. Es ist im Grunde nur eine Breitensuche, bis es einen Platz findet, an dem es den Knoten einfügen kann.

Beachten Sie, dass Sie dazu einen speziellen "Nullknoten" einfügen müssen, wenn der Benutzer "-" eingibt. Sie können einen boolean-Flag in Ihrer TreeNode Klasse für diesen Einsatz:

class TreeNode { 
    int data; 
    boolean isNull; 
    TreeNode LC, RC; 

    public TreeNode(int x) { 
     data = x; 
     LC = null; 
     RC = null; 
    } 

    public TreeNode() { 
     isNull = true; 
    } 
} 

Schließlich können Sie den Einsatz -Methodenüberladung Null Knoten einzufügen, wenn der Benutzer gefragt. Die überladene Funktion ist das gleiche, außer dass es neue TreeNodes erstellt den Standard-Konstruktor:

public static void insert(TreeNode root) { 
    Queue<TreeNode> q = new LinkedList<TreeNode>(); 
    q.offer(root); 

    while(!q.isEmpty()) { 
     TreeNode u = q.poll(); 

     if(u.LC == null) { 
      u.LC = new TreeNode(); 
      break; 
     } 

     if(u.RC == null) { 
      u.RC = new TreeNode(); 
      break; 
     } 

     if(!u.LC.isNull) 
      q.offer(u.LC); 

     if(!u.RC.isNull) 
      q.offer(u.RC); 
    } 
} 

Ihre Hauptmethode würde dann wie folgt aussehen:

public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    int x = input.nextInt(); 
    TreeNode root = new TreeNode(x); 

    while(true) { 
     String str = input.next(); 
     if(str.equals("-")) 
      insert(root); 
     else 
      insert(root, Integer.parseInt(str)); 
    }  
}