1。コンセプト
バイナリ検索ツリーもバイナリソートツリーになります。ノードに2つの子ノードがある場合、満たす必要があるという特徴があります。左の子ノードの値はノードの値よりも小さくなければならず、右の子ノードの値はノードの値よりも大きくなければなりません。非基準タイプの比較のために、コンパレータインターフェイスを実装できます。この記事では、intタイプデータが操作に使用されます。
バイナリツリーを実装するには、その増加から始めなければなりません。ツリーを構築することによってのみ、他の操作を使用できます。
2。バイナリ検索ツリーの構築
バイナリツリーの増加について話すときは、最初にノードを表すクラスを構築する必要があります。ノードのクラスには、ノードの値、親ノード、左ノード、ノードの右ノードといういくつかの属性があります。コードは次のとおりです
static class node {node parent; Node LeftChild;ノード右チャイルド; int val; public node（ノード親、ノードleftchild、node rightchild、int val）{super（）; this.parent = parent; this.leftchild = leftchild; this.rightchild = rightchild; this.val = val; } public node（int val）{this（null、null、null、val）; } public node（node node、int val）{this（node、null、null、val）; }}ここでは、内部クラスの書き込み方法を使用します。ノード値を構築した後、ツリー全体を構築します。ツリーは最初にルートノードを持ち、次に残りの子ノードに拡張する必要があります。このツリーには、基本的なルートノードルートやツリーの要素サイズなど、いくつかの属性もあります。これらの2つの属性を使用すると、Comparator属性が追加されるか、デフォルトの実装が提供される場合があります。特定のコードは次のとおりです
パブリッククラスSearchBinaryTree {プライベートノードルート;プライベートINTサイズ。 public searchbinarytree（）{super（）; }}3。追加
要素を追加するときは、ルートノードの初期化を考慮する必要があります。一般に、2つのタイプがあります。このクラスのコンストラクターが初期化されると、ルートノードルートが初期化されます。 2つ目は、最初の要素が追加されたときにルートノードを追加することです。どちらも理論的には機能しますが、通常は2番目の怠zyなロードフォームを使用します。
要素を追加するとき、考慮する必要があるいくつかの状況があります
1.追加するときは、ルートが初期化されているかどうかを判断します。初期化されていない場合、初期化されます。ルートノードに値を割り当て、1つのサイズを追加します。
2。バイナリツリー検索ツリーは、ルートノード値が左ノードよりも大きく、右ノードよりも小さいことを満たすため、挿入された値を最初にルートノードと比較する必要があります。大きい場合は、右のサブツリーで検索します。小さい場合は、左サブツリーで検索します。子ノードまで。
ここでの挿入実装では、1つ、再帰、2つ、反復的な2つのタイプを採用できます（つまり、ループモードを介して）。
3.1。再帰バージョンの挿入
public boolean add（int val）{if（root == null）{root = new node（val）;サイズ++; trueを返します。 } node node = getadapternode（root、val）;ノードnewNode = new Node（val）; if（node.val> val）{node.leftchild = newNode; newNode.Parent = node; } else if（node.val <val）{node.rightchild = newNode; newNode.Parent = node; } else {//当時の処理なし} size ++; 19 return true; } /***挿入するノードの親ノードを取得します。親ノードは次の状態のいずれかを満たします* 1。親ノードは子ノード* 2です。挿入ノードの値は親ノードよりも小さくなりますが、親ノードには左の子供ノードがありません* 3。 * 5。親ノードは空です*上記の5つのケースのいずれかが満たされている場合、再帰的に停止します。 * @param node * @param val * @return */ private node getadapternode（node node、int val）{if（node == null）{return node; } //左サブツリーに挿入しますが、左サブツリーはありません。 } //右サブツリーに挿入しますが、右サブツリーはありません。また、if（node.val <val && node.rightchild == null）{return node; } //右サブツリーに挿入しますが、右サブツリーはありません。また、if（node.val <val && node.rightchild == null）{return node; } //右サブツリーに挿入しますが、右サブツリーはありません。また、if（node.val <val && node.rightchild == null）{return node; } //右のサブツリーに挿入しますが、右サブツリーはありません、if（node.leftchild == null && node.rightchild == null）{return node; } if（node.val> val && node.leftchild！= null）{return getAdaptarNode（node.leftchild、val）; } else if（node.val <val && node.rightchild！= null）{return getadaptarnode（node.rightchild、val）; } else {return node; }}再帰を使用し、最初に再帰の終点を見つけてから、問題全体をサブ問題に変えます。上記のコードでは、ロジックはほぼこのようなものです。最初にルートノードが初期化され、初期化されていない場合、初期化され、完了後に戻り、関数を使用して適応したノードを取得します。次に、値を挿入します。
3.2。反復バージョン
public boolean put（int val）{return putval（root、val）; } private boolean putval（node node、int val）{if（node == null）{// root node node = new node（val）; root = node;サイズ++; trueを返します。 } node temp = node;ノードP; int t; / ** *ループ繰り返しを介して最適なノードを取得します */ do {p = temp; t = temp.val-val; if（t> 0）{temp = temp.leftchild; } else if（t <0）{temp = temp.rightchild; } else {temp.val = val; falseを返します。 }} while（temp！= null）;ノードnewNode = new Node（P、Val）; if（t> 0）{p.leftChild = newNode; } else if（t <0）{p.RightChild = newNode; } size ++; trueを返します。 }原則は実際には再帰と同じです。これは、最適なノードを取得してそのノードで動作することです。
パフォーマンスに関しては、間違いなく最高の反復バージョンであるため、一般に、データを動作させるのは反復バージョンです。
4.削除
バイナリ検索ツリーの操作では、削除が最も複雑であり、考慮すべき比較的多くの状況があると言えます。従来の方法では、バイナリ検索ツリーのノードを削除すると、次の4つの状況を間違いなく考えることができます。
1.削除するノードには、上の図のd、e、およびgノードに示されているように、左および右の子ノードはありません
2。削除するノードは、ノードBなどの左子ノードのみです
3.削除するノードは、Fノードなどの適切な子ノードのみです
4.削除するノードには、AやCノードなどの左子ノードと右の子ノードの両方があります
最初の3つの状況では、それは比較的単純であり、4番目の状況は複雑であると言えます。最初のものを分析しましょう
たとえば、この場合、ノードDが削除されている場合、ノードBの左子ノードをnullに設定し、ノードGが削除された場合、ノードFの右子ノードをnullに設定できます。どちらの側を設定する必要があり、削除されたノードがどの側面が配置されているかを確認します。
ノードBを削除する2番目の方法では、ノードAの左ノードをノードDに設定し、ノードDの親ノードをAに設定するだけです。
3番目のタイプは、2番目のタイプと同じです。
前述のように少し複雑な4番目のタイプは、たとえば、cノードを削除し、fノードの親ノードをノードAに設定し、fノードの左ノードをノードeに設定するためです。では、どちらを使用する必要がありますか？削除ノードがルートノードである場合、どのように削除する必要がありますか？
4番目のケースでは、このように考えることができます。Cまたはノードの後継ノードを見つけ、後継ノードを削除し、後継ノードの値をCまたはAノードの値に設定します。まず、後継ノードの概念を補いましょう。
ツリー全体のノードの後継ノードが満たされる必要があります。ノードに値するノードのセットに最小値のノードは、後継ノードです。もちろん、後継ノードがない場合があります。
ただし、4番目のケースでは、後継ノードが存在する必要があり、その右サブツリーにある必要があり、子供のノードが1つしかないか、子ノードがない場合の1つを満たしています。後継ノードはCノードよりも大きいため、Cノードの左右のサブセクションが存在する必要があるため、右サブツリーの左サブセクションに存在する必要があるため、特定の理由を考えることができます。たとえば、Cの後継ノードはFであり、Aの後継ノードはEです。
上記の分析では、実装は比較的簡単で、コードは次のとおりです。
public boolean delete（int val）{node node = getNode（val）; if（node == null）{return false; } node parent = node.parent; node leftchild = node.leftchild; node rightchild = node.rightchild; //次のすべての親ノードは空です。これは、削除されたノードがルートノードであることを意味します。 } else if（parent.rightchild == node）{parent.rightchild = null; }} else {//親ノードは存在しません。つまり、削除されたノードはルートノードルート= nullです。 } node = null; trueを返します。 } else if（leftchild == null && rightchild！= null）{//右ノードのみ（parent！= null && parent.val> val）{//親ノードがあり、ノードの位置は親ノードの左側です。 } else if（parent！= null && parent.val <val）{//親ノードがあり、ノードの位置は親ノードparent.rightchild = rightchild; } else {root = rightchild; } node = null; trueを返します。 } else if（leftchild！= null && rightchild == null）{//左ノードのみ（parent！= null && parent.val> val）{//親ノードがあり、ノードの位置は親ノードの左側です。 } else if（parent！= null && parent.val <val）{//親ノードがあり、ノードの位置は親ノードparent.rightchild = leftchild; } else {root = leftchild; } trueを返します。 } else if（leftchild！= null && rightchild！= null）{//両方の子ノードはノード後継者= getSuccesser（node）; // boolean delete = delete（temp）; if（delete）{node.val = temp; }後継者= null; trueを返します。 } falseを返します。 } /***ノードノードの後継ノードを見つけます*1。最初に、ノードに右サブツリーがあるかどうかを判断します。その場合、右ノードの左サブツリーから後継ノードを探してください。そうでない場合は、次のステップ* 2に進みます。ノードの親ノードを見つけます。親ノードの右ノードがノードに等しい場合、親ノードがnullになるか、ノードに等しくない右ノードを見つけるまで、親ノード *を探し続けます。 *理由、後継ノードはノードよりも大きくなければなりません。右のサブツリーがある場合、後継ノードは右サブツリーに存在する必要があります。これが最初のステップ*の理由です*右のサブツリーがない場合、ノードの祖父ノード（つまり、ノードの親ノード、または親ノードの上の親ノード）もあります。 *繰り返し検索しますが、ある場合はノードを返し、nullを返します * @param node * @return */ private node getsuccesser（node node）{if（node.rightchild！= null）{node rightchild = node.rightchild; while（rightchild.leftchild！= null）{rightchild = rightchild.leftchild; } returtchild; } node parent = node.parent; while（parent！= null &&（node == parent.rightchild））{node = parent;親= parent.parent; }親を返します。 }特定のロジックについては、上記の分析を参照してください。ここではテキストについては説明しません。
この実装に加えて、アルゴリズムの紹介で別の実装が提供されています。
public boolean remove（int val）{node node = getNode（val）; if（node == null）{return false; } if（node.leftchild == null）{// 1。左ノードが存在しない場合、2つの状況を含む右ノードが存在する可能性があります。どちらのノードも存在せず、右ノードのみが移植（ノード、ノード.RightChild）が存在します。 } else if（node.rightchild == null）{// 2。左の子供が存在し、右のノードは移植されません（ノード、node.leftchild）。 } else {//3。両方のノードはノード後継者= getSuccessor（node）; //ノード後継ノードを取得する場合（後継者！= node）{//後継ノードはノードの右サブツリーに存在します。移植（後継者、後継者.RightChild）; //後継者を後継者の右子ノードに置き換えます。移植（ノード、後継者）;後継者。LeftChild= node.leftchild;後継者。LeftChild.Parent=後継者; } trueを返します。 } /***子ノードをノードノードに置き換えますステップ*2。ノードノードが親ノードの子であること（つまり、ノードが右ノードか左ノードかどうかを判断する）、*結果を取得した後、子ノードノードをノードノードに置き換えること、つまりノードノードが左ノードの場合、子供は左ノードになります。 node*/ if（node.parent == null）{this.root = child; } else if（node.parent.leftchild == node）{node.parent.leftchild = child; } else if（node.parent.rightChild == node）{node.parent.rightChild = child; } if（child！= null）{child.parent = node.parent; }}5。検索
検索も比較的簡単ですが、実際には、追加されると実装されています。実際の状況では、この部分は別の方法から抽出できます。コードは次のとおりです
public node getNode（int val）{node temp = root; int t; {t = temp.val-val; if（t> 0）{temp = temp.leftchild; } else if（t <0）{temp = temp.rightchild; } else {return temp; }} while（temp！= null）; nullを返します。 }6。バイナリ検索ツリートラバーサル
バイナリ検索ツリーの特性を理解した後、その中間順序トラバーサルが小さいから大規模に順番に配置されていることは明らかです。ここに記載されている中間注文トラバーサルコードは次のとおりです
public void print（）{print（root）; } private void print（node root）{if（root！= null）{print（root.leftchild）; System.out.println（root.val）; //位置が中央にある場合、順序は中央にあります。それが正面にある場合、それは先例です、そうでなければそれは後続の印刷（root.rightchild）です。 }}要約します
上記は、エディターによって導入されたバイナリ検索ツリー機能のJava実装です。私はそれが誰にでも役立つことを願っています。ご不明な点がございましたら、メッセージを残してください。編集者は、すべての人に時間内に返信します！