バイナリツリー、迅速な実装

学生には、一見簡単に見えるタスクが割り当てられている場合があり、完了した場合にのみ、彼らの本当の複雑さを理解できます。

これらのタスクの1つは、コレクションクラス「バイナリツリー」を作成することです。 詳細はこちら 。 必要に応じて、経験豊富なプログラマーがより適切に記述します。簡単な実装を次に示します。

そのため、次のスキームを使用することが決定されました。

class BinaryTree{ private static class BinaryTreeElement{ public Comparable object; public BinaryTreeElement leftChild; public BinaryTreeElement rightChild; } private BinaryTreeElement root; public boolean isEmpty(); public boolean add(Comparable o); public boolean delete(int number); public Object[] output(); public Object[] toArray(); } Interface Comparable{ public int CompareTo(Object o); public int nextNumber(); public int getNumber(); } 

まず最初に。 BinaryTreeクラスには、ツリーの非表示のサブクラスノードが含まれます。 各バイナリツリーノードには、左および右の子孫ノードと格納されたオブジェクトが含まれます。 オブジェクトは、ツリーノードにオブジェクトを正しく配置するために使用されるメソッドを含む、作成されたComparableインターフェイスを実装します。

1. 「オブジェクトを比較する方法は？」という質問に対する答えを取得する方法 どれが現在のもの（this）なのか、それともメソッドに渡されたものなのでしょうか？
2. 以前に追加された要素のいずれかの番号と一致する番号を持つ要素を追加しようとしたときに、プログラムのアルゴリズムを決定する方法。
3. アイテムをコレクションに正しく追加するためにアイテム番号を取得するために使用されるメソッド。

BinaryTreeElementクラスの残りの2つの要素は、このノードの子孫ノードを格納するために必要です。 各ノードはフラクタルであり、退屈するか、コンピューターリソースがなくなるまで、ツリーに要素を追加できます。

それでは、BinaryTreeクラスに直接移動しましょう。 このクラスには、ルートルートノードと、それとその子孫を操作するためのメソッドが含まれます。 これらの方法については、以下で詳しく説明します。

1. ツリー要素を取得しようとしたときにユーザーに例外をスローしないようにするには、このツリーに要素があるかどうかを判断するメソッドを作成するとよいでしょう。 さらに、非常に簡単です。
   
   

    public boolean isEmpty(){ return root==null; } 

2. 要素を追加できないコレクションが必要なのはなぜですか？ したがって、add（）メソッドを実装します。
   
   このメソッドは、バイナリツリー内の要素の位置を正しく決定する必要があります。したがって、要素の番号を取得できる必要があります。 このコレクションの機能を、動作可能な1つのクラスのみに制限しないために、Comparableインターフェイスが作成されました。
   
   ツリーの各要素はフラクタルです。つまり、この状況での再帰関数は理想的です。 ただし、再帰的なメソッドを実装する場合、このメソッドには、ローカル（このメソッドのみ）をルートと見なす要素が必要です。 呼び出されると、（追加された要素がルート右、左下よりも大きい場合）ステップする方法を決定し、対応する子孫を再帰的に渡します。 同時に、ユーザーはノードに直接アクセスできません。=>このメソッドのローカルルートである開始点を決定できません。したがって、2つのメソッドがここで実装されます。
   追加されたアイテムに以前に追加されたアイテムの番号と一致する番号がある場合、メソッドが呼び出されて新しいアイテムの番号が変更され、例外がスローされます。 例外を使用して、呼び出し元の（パブリック）メソッドに戻り、再帰をリセットし、リストの先頭から要素の場所を探します。
   
   

    public boolean add(Comparable o){ while(true) { try { root = add(o, root); break; }catch(ArrayStoreException e){ continue; } } return true; } private BinaryTreeElement add(Comparable o,BinaryTreeElement element){ if(element==null){ element=new BinaryTreeElement(); element.object=o; return element; } else { //     while(o.CompareTo(element.object) == 0) { o.nextNumber(); //     ()           throw new ArrayStoreException(); } if (o.CompareTo(element.object) > 0) { //  element.rightChild = add(o, element.rightChild); return element; } else { //  element.leftChild = add(o, element.leftChild); return element; } } } 

   
   
3. 次に、コレクションからアイテムを削除する機能を追加します。 削除する要素に子がない場合、この機能は難しくありません。その安全性を心配して要素を破壊することはできません。 そうでない場合は、削除する要素の子孫ブランチを保存し、必要な要素を削除し、add（BinaryTreeElement要素、ブール値b）メソッドを使用して、保存したブランチの要素をコレクションに再帰的に追加します。
   
   オブジェクトは参照データ型であるため、現在のオブジェクトをnullにすることはできません。代わりに、親は要素へのリンクを削除する必要があるため、コードは複雑に見えます。
   子孫を持つノードを削除する戦術は、右の子孫（右のサブツリー）で最小要素を検索し、削除された要素を見つかった要素で置き換えることです。 特定のサブツリー内の最小要素を見つけるには、deleteMinChild（）メソッドを使用します
   
   

    public Comparable delete(int number)throws NullPointerException { if (root == null) throw new NullPointerException(); //,         Comparable object; //      ,           if (root.object.getNumber() == number) { object = root.object; if (root.leftChild == null) { if (root.rightChild == null) root = null; else root = root.rightChild; } else { if (root.rightChild == null) { if (root.leftChild == null) root = null; else root = root.leftChild; } else { if (root.leftChild != null && root.rightChild != null) { try { BinaryTreeElement element=deleteMinChild(root.rightChild); root.object = element.object; add(element,false); }catch(NullPointerException e){ // ,       ,     root.rightChild.leftChild=root.leftChild; root=root.rightChild; } } } } return object; } object=delete(number, root); return object; } private BinaryTreeElement deleteMinChild(BinaryTreeElement element){ if(element.leftChild.leftChild==null){ BinaryTreeElement find=element.leftChild; element.leftChild=null; return find; } return deleteMinChild(element.leftChild); } private Comparable delete(int number, BinaryTreeElement element) throws NullPointerException{ //   Comparable result=null; //   if(element.object.getNumber() < number) { //    if (element.rightChild.object.getNumber() == number) { // -  result = element.rightChild.object; //  -   ,    if (element.rightChild.leftChild == null && element.rightChild.rightChild == null) element.rightChild = null; else { if(element.rightChild.leftChild!=null && element.rightChild.rightChild!=null){ try { BinaryTreeElement newElement = deleteMinChild(element.rightChild.rightChild); element.rightChild.object=newElement.object; add(newElement,false); }catch(NullPointerException e){ // ,              element.rightChild.rightChild.leftChild=element.rightChild.leftChild; element.rightChild=element.rightChild.rightChild; } } else { if (element.rightChild.leftChild == null) element.rightChild = element.rightChild.rightChild; else { if (element.rightChild.rightChild == null) element.rightChild = element.rightChild.leftChild; } } } } else{ result=delete(number,element.rightChild); } } //   else { if (element.leftChild.object.getNumber() == number) { // -  result = element.leftChild.object; //  -   ,    if (element.leftChild.leftChild == null && element.leftChild.rightChild == null) element.leftChild = null; else { if (element.leftChild.leftChild!=null && element.leftChild.rightChild!=null){ try{ BinaryTreeElement newElement = deleteMinChild(element.leftChild.rightChild); element.leftChild.object=newElement.object; add(newElement,false); }catch(NullPointerException e){ // ,              element.leftChild.rightChild.leftChild=element.leftChild.leftChild; element.leftChild=element.leftChild.rightChild; } } else{ if(element.leftChild.rightChild==null) element.leftChild=element.leftChild.leftChild; else{ if(element.leftChild.leftChild==null) element.leftChild=element.leftChild.rightChild; } } } } else{ result=delete(number,element.leftChild); } } return result; } 

4. ツリーのコンテンツを美しく出力するために、output（）メソッドが実装されています。 このメソッドは、バイナリツリーをスキャンし、最小値から始めてすべての要素を表示します。インデントにより、ノードのネストを追跡できます。 ユーザーに表示されるメソッドとプライベートのメソッドも2つあります。
   
   

    public Object[] output(){ if(root!=null) return output(root); return new String[]{"    "}; } private Object[] output(BinaryTreeElement element) { ArrayList<String> result = new ArrayList<>(); if (element.leftChild != null) { Object[] temp = output(element.leftChild); for (int i = 0; i < temp.length; i++) { result.add(" "+ temp[i]); } } result.add(element.object.toString()); if (element.rightChild != null) { Object[] temp = output(element.rightChild); for (int i = 0; i < temp.length; i++) { result.add(" " + temp[i]); } } return result.toArray(); } 

5. バイナリツリーの内容を配列の形式で取得することができます。配列の要素は、下位（数値が小さい）から大きい順にソートされます。 コレクションに要素がない場合、このメソッドはNullPointerExceptionをスローするため、呼び出す前にisEmpty（）メソッドを使用することをお勧めします。 このメソッドはoutput（）メソッドに非常に似ていますが、オブジェクトの文字列の説明ではなく、オブジェクト自体を返します。
   
   

    public Object[] toArray(){ if(root==null) throw new NullPointerException(); return toArray(root); } private Object[] toArray(BinaryTreeElement element){ ArrayList<Comparable> result=new ArrayList<>(); if (element.leftChild != null) { Object[] temp = toArray(element.leftChild); for (int i = 0; i < temp.length; i++) { Comparable object=(Comparable)temp[i]; result.add(object); } } result.add(element.object); if (element.rightChild != null) { Object[] temp = toArray(element.rightChild); for (int i = 0; i < temp.length; i++) { Comparable object=(Comparable)temp[i]; result.add(object); } } return result.toArray(); } 

開発されたクラス、Comparableインターフェイスを実装するクラス、およびこのクラスの要素をコレクションに追加するプログラムの完全なコードはこちらです。

私は実装がかなり弱いことを理解しています。開発されたクラスを改善するための提案は大歓迎です。