Javaでバイナリツリーを入力する方法

Question

Javaでバイナリツリーを実装するのに助けが必要です。

私はテキストファイルからそれを読むのと同じではありません。ユーザーがスキャナを使用してツリーを入力した後、ツリー値を作成して出力することを意味します。また、「 - 」記号はツリー内のヌル値を意味します。

これまでのところ、ノードクラスが動作していますが、私はそれが前記ノードからツリーを作ることができるようにする必要があります。また、入力の受け入れを停止する時期も知っておく必要があります。

ここに私のコードがあります。私はノードのリストを入力し、これらのクラスを使ってツリーにする方法が必要です。例えば、同様

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

    } 

、人が入力した場合、この - それは、このようなツリーにそれを整理することになる

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

（あるヌルノード）。

  1 
    / \ 
     2  3 
     \ /\ 
     4 5 6 

誰でも役に立つと思いますか？キューが必要だと思う。また、入力の受け入れをいつ止めるかを知る方法を教えてください。

Answer 1

数値をチェックして、たとえば親よりも大きい数字を右に追加するメソッドを開発する必要があります。親より小さい場合は左に追加する必要があります。あなたは再帰の助けを借りてこの機能を開発できると思います。

Answer 2

新しいノードをレベルごとに左から右に挿入しようとする関数です。基本的には、ノードを挿入できる場所が見つかるまで幅優先探索を行います。

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

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

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

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

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

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

この機能を有効にするには、ユーザーが「 - 」を入力するたびに特別な「ヌル」ノードを挿入する必要があります。あなたはこのためにあなたのTreeNodeクラスのブールフラグを使用することができます。

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

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

    public TreeNode() { 
     isNull = true; 
    } 
} 

最後に、あなたがユーザーによって要求されたときにヌルノードを挿入するInsertメソッドをオーバーロードすることができます。オーバーロードされた関数は、それがデフォルトコンストラクタを使用して新しいのTreeNodeを作成することを除いて同じである：

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

あなたの主な方法は次のようになります。

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