1つは、バイナリソーティングツリー定義です
1。バイナリソーティングツリーの定義<br />バイナリソートツリー（バイナリソートツリー）、バイナリ検索ツリーとしても知られています。次のように定義されています。バイナリソーティングツリーまたは空のツリー、または次の特性を満たすバイナリツリー：
左サブツリーが空でない場合、左サブツリーのすべてのノードの値はルートノードの値よりも小さくなります。
右のサブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値よりも大きくなります。
左左右のサブツリー自体は、それぞれバイナリソートツリーです。
上記のプロパティは、バイナリソーティングツリープロパティ（BSTプロパティ）と呼ばれるため、バイナリソートツリーは実際にはBSTプロパティを満たすバイナリツリーです。
2。バイナリソートツリーのプロパティ<br />バイナリソーティングツリーを中間で転送すると、結果の中間順方向トラバーサルシーケンスは増分順序付きシーケンスです。
3.バイナリソートツリーを挿入<BR />バイナリソーティングツリーに新しいノードを挿入して、挿入されたバイナリツリーがバイナリソートツリーの定義をまだ満たしていることを確認します。
プロセスを挿入：
バイナリソートツリーが空の場合、ルートノードとして空のツリーに挿入されるノード *s。
空でない場合は、キーワードs->キーをツリールートキーワードt-> keyに挿入するキーワードを比較します。 s-> key = t-> keyの場合、挿入する必要はありません。 s-> key <t->キーの場合、ルートの左サブツリーに挿入されます。 s-> key> t-> keyの場合、ルートの右サブツリーに挿入されます。サブツリーの挿入プロセスは、ツリーの挿入プロセスと同じです。これは、ノード *sが新しいリーフとしてバイナリソートツリーに挿入されるか、ツリーが同じキーワードを持つノードがあることがわかったまで続きます。
4.バイナリソートツリーの検索<BR />バイナリソートツリーのルートポインターがルートであり、指定されたキーワード値がKであると仮定すると、検索アルゴリズムは次のように説明できます。
①初期値を設定：q = root;
k = q->キーの場合、検索が成功し、アルゴリズムが終了します。
それ以外の場合、k <q qキーとqの左サブツリーが空でない場合、qの左サブツリーがqに送信され、次にステップ②に送信されます。それ以外の場合、検索が失敗し、アルゴリズムが終了します。
それ以外の場合、k＞q＞キーであり、qの右サブツリーが空でない場合、qの右サブツリーがqに送信され、次にステップ②が送信されます。それ以外の場合、検索が失敗し、アルゴリズムが終了します。
5.バイナリソートツリーの削除<br />削除されたノードが *pであり、親が *fであると仮定します。これは一般性では失われていません。 *pは *fの左の子であると仮定し、次の状況に分かれています。
nodeノード *pがリーフノードの場合、親ノードのポインターを変更するだけでいいです *f。
nodeノード *pに左サブツリーPLまたは右サブツリーPRのみがある場合、PLまたはPRを親ノードの左サブツリーに作成します。
nodeノード *pの左と右のサブツリーが空でない場合、最初に *pのミドルオーダーの前身（または後継）ノード *sを見つけます（ *sは *pの左サブツリーの右下ノードであり、右のチェーンドメインは空です）。次に、2つの方法があります。 *Pの中心部の前身ノード *の右チェーンに。 * *pの中央順序の前身ノード *s（つまり、 *sのデータを *pにコピー）に置き換え、 *sの左側のサブツリーを親ノードの左（または右）チェーンにチェーンします。
6.バイナリツリーの横断<br />次のように、バイナリツリーを通過する3つの方法があります。
（1）先行トラバーサル（DLR）、最初にルートノードにアクセスし、次に左サブツリーを通過し、最後に右サブツリーを通過します。省略されたルート - 左 - 右。
（2）順序トラバーサル（LDR）、最初に左サブツリーを通過し、次にルートノードにアクセスし、最後に右サブツリーを通過します。略語メモ：左根右。
（3）ポストオーバートラバーサル（LRD）、最初に左サブツリーを横断し、次に右サブツリーを通過し、最後にルートノードにアクセスします。左右に略された。
2。コードライティング
1。ツリーノードクラス0の定義
パッケージcom.lin; / ** *関数概要： */ public class treeNode {public Integer Data; /*このノードの親ノード*/ public Treenode parent; /*このノードの左子ノード*/ public Treenode左; /*このノードの右子ノード*/ public treenode右; public Treenode（integer data）{this.data = data; } @Override public String toString（）{return "treenode [data =" + data + "]"; }} 2。バイナリソーティングツリーの定義
パッケージcom.lin; /***関数の概要：ソート/バランスの取れたバイナリツリー*/public class searchTree {public treenode root;パブリックロングサイズ。 / ** *ツリーにノードを追加 * @param data * @return boolean挿入true */ public boolean addtreenode（integer data）{if（null == root）{root = new Treenode（data）; System.out.println（ "データはバランスの取れたバイナリツリーに正常に挿入されました"）; trueを返します。 } treenode treenode = new Treenode（data）; //挿入されるデータtreeNode currentNode = root; treenode parentnode; while（true）{parentNode = currentNode; //親ノードを保存//挿入されたデータは親ノードよりも小さいif（currentNode.data> data）{currentNode = currentNode.Left; //現在の親ノードの左の子ノードは空です（null == currentNode）{parentNode.left = treenode; treenode.parent = parentnode; System.out.println（ "データはバイナリ検索ツリーに正常に挿入されました"）;サイズ++; trueを返します。 } //挿入されたデータは親ノードよりも大きいです//現在の親ノードの右子ノードは空です（null == currentNode）{parentNode.right = treenode; treenode.parent = parentnode; System.out.println（ "データはバイナリ検索ツリーに正常に挿入されます"）;サイズ++; trueを返します。 }} else {system.out.println（ "入力データはノードのデータと同じです"）; falseを返します。 }}} / ** * @param data * @return treenode * / public treeNode findtreenode（integer data）{if（null == root）{return null; } treenode current = root; while（current！= null）{if（current.data> data）{current = current.left; } else if（current.data <data）{current = current.right; } else {return current; }} nullを返します。 }}追加と検索の方法は次のとおりです
3。フロント、ミドル、バックトラバーサル
パッケージcom.lin; java.util.stackをインポートします。 / **関数の概要：*/ public class treeOrder {/ ***予約注文トラバーサルの再帰実装* @author linbingwen* @since 2015年8月29日*/ public static void preodermethodone（treeNode treeNode）{if（null！= treenode）{system.out.print（ "）; if（null！= treenode.left）{preordermethodone（treenode.left）; } if（null！= treenode.right）{preordermethodone（treenode.right）; }}} / ***事前注文トラバーサルを実装するループ* @param treenode* / public static void preodermethodtwo（treenode treenode）{if（null！= treenode）{stack <treenode> stack = new stack <treenode>（）; stack.push（treeNode）; while（！stack.isempty（））{treenode tempnode = stack.pop（）; System.out.print（tempnode.data + ""）; //右の子ノードはnullではありません。if（null！= tempnode.right）{stack.push（tempnode.right）; } //右の子ノードを置いた後、左の子ノードを入れて、if（null！= tempnode.left）{stack.push（tempnode.left）; }}}}} / ***再帰的に順序を実装します* @param treenode* / public static void medordermethodone（treeNode treenode）{if（null！= treened）{if（null！= treeNode.left）{medordermethodone（treenode.left）; } system.out.print（treenode.data + ""）; if（null！= treenode.right）{medordermethodone（treenode.right）; }}} / ***ループ実装インターントラバーサル* @param treenode* / public static void medordermethodtwo（treeNode treenode）{stack <treenode> stack = new stack <treenode>（）; treeNode current = treeNode; while（current！= null ||！stack.isempty（））{while（current！= null）{stack.push（current）; current = current.left; } if（！stack.isempty（））{current = stack.pop（）; System.out.print（current.data+""）; current = current.right; }}} / ***再帰的な順序トラバーサル* @param treeNode* / public static void postordermethodone（treeNode treenode）{if（null！= treeNode）{（null！= treenode.left）{postordermethodone（treenode.left）; } if（null！= treenode.right）{postordermethodone（treenode.right）; } system.out.print（treenode.data + ""）; }} / ***順番トラバーサルを実装するループ* @param treenode* / public static void postordermethodtwo（treenode treenode）{if（null！= treenode）{stack <treenode> stack = new stack <treenode>（）; treeNode current = treeNode; treenode rednode = null; while（current！= null ||！stack.isempty（））{while（current！= null）{stack.push（current）; current = current.left; } current = stack.pop（）; while（current！= null &&（current.right == null || current.right == rightnode））{system.out.print（current.data + ""）; rightnode = current; if（stack.isempty（））{system.out.println（）;戻る; } current = stack.pop（）; } stack.push（current）; current = current.right; }}}} 4。使い方
パッケージcom.lin; / ** *関数概要： */ public class searchTreeTest {/ ** * @param args */ public static void main（string [] args）{searchTree tree = new SearchTree（）; tree.addtreenode（50）; tree.addtreenode（80）; tree.addtreenode（20）; tree.addtreenode（60）; tree.addtreenode（10）; tree.addtreenode（30）; tree.addtreenode（70）; tree.addtreenode（90）; tree.addtreenode（100）; tree.addtreenode（40）; System.out.println（ "=============================================================================================================== ========================================================================== =============================================================================== ========================================================================== =============================================================================== =============================================================================== =============================================================================== System.out.println（ "===================================================== ============================================================================= ============================================================================= ============================================================================ ============================================================================= ============================================================================= ============================================================================= ============================================================================ treeOrder.PostOrderMethodone（tree.root）; out.println（）; System.out.println（ "=========================================================================================================== =============================================================================== =============================================================================== =============================================================================== =============================================================================== =============================================================================== =============================================================================== System.out.println（ "===================================================== ============================================================================= ============================================================================= ============================================================================ ============================================================================= ============================================================================= ============================================================================= ============================================================================ treeOrder.MedORDEMETHODTWO（tree.Root）}}出力結果：
同様に、検索プロセスは次のとおりです。
treenode node = tree.findtreenode（100）; System.out.println（node）;
結果は正しいです
上記は、Javaバイナリソートツリーの詳細な紹介です。 Javaプログラミングを皆さんの学習に役立つことを願っています。