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プログラミングを皆さんの学習に役立つことを願っています。