Java プログラミング スキル - データ構造とアルゴリズム「ツリー」

[[388287]]

なぜツリー構造が必要なのでしょうか?

1. 配列格納方法の分析:

• 利点: 下付き文字で要素に高速にアクセスします。順序付けられた配列の場合、バイナリ検索を使用して検索速度を上げることもできます。
• デメリット: 特定の値を取得したり、値を挿入したり (特定の順序で) すると、テーブル全体が移動されるため、非効率的です。

2. チェーンストレージ方式の分析：

• 利点: ある程度、配列の保存方法を最適化します (たとえば、数値ノードを挿入するには、挿入されたノードをリンク リストにリンクするだけでよく、削除効率が非常に高くなります)。
• デメリット: 検索を実行する場合、効率は依然として非常に低く、最初のノードからトラバースする必要があります。

3. ツリー保存方法の分析：データの保存と読み取りの効率を向上させることができます。たとえば、バイナリソートツリーを使用すると、データ検索の速度が保証されるだけでなく、データの挿入、削除、変更の速度も保証されます。集合[7,3,10,1,5,9,12]がツリーに格納されており、分析は次のようになると仮定します。

二分木の前順、中順、後順の走査

• 事前順序トラバーサル: 親ノードを出力し、左ノードを出力し、右ノードを出力します。
• 順序どおりのトラバーサル: 左のノードを出力し、親ノードを出力し、右のノードを出力します。
• 後順トラバーサル: 左ノードを出力し、右ノードを出力し、親ノードを出力します。

需要事例

次のバイナリ ツリー ノードの保存、事前順序トラバーサル検索、順序内トラバーサル検索、事後順序トラバーサル検索、およびノー​​ド削除機能を完了します。

ノードを削除するための要件は次のとおりです。

1. 削除するノードがリーフノードの場合は、そのノードを削除します。
2. 削除されるノードが非リーフノードの場合、ツリーは削除されます。
3. テストして、リーフ ノード 5 とサブツリー 3 を削除します。

コード例

パッケージ com.xie.tree; 
 
パブリッククラス BinaryTreeDemo { 
 
公共 静的void main(String[] args) {
        バイナリツリー binaryTree = new BinaryTree(); 
 
        HeroNode ルート = new HeroNode(1, "Song Jiang" );
        HeroNode node2 = 新しいHeroNode(2, "Wu Yong" );
        HeroNode node3 = 新しい HeroNode(3, "Lu Junyi" );
        HeroNode node4 = 新しい HeroNode(4, "Lin Chong" );
        HeroNode node5 = 新しい HeroNode(5, "Guan Sheng" ); 
 
        // まず手動でバイナリツリーを作成し、次に再帰を使用します
        ルート.setLeft(ノード2);
        ルートを右に設定します(ノード3);
        ノード4を右に設定します。
        ノード3を左に設定します(ノード5); 
 
        バイナリツリーのルートを設定します。 
 
        // 事前順序トラバーサル
        System.out.println ( "事前順序トラバーサル" );
        バイナリツリーの事前順序付け(); 
 
        // 順序通りの走査
        System.out.println ( "順序通りの走査" );
        バイナリツリーの順序を固定します。 
 
        //後続のトラバーサル
        System.out.println ( "後続のトラバーサル" ) ;
        バイナリツリーの postOrder() を返します。 
 
        // 先行順序トラバーサル検索
        System.out.println ( "事前順序トラバーサル検索~~" );
        HeroNode の結果ノード = binaryTree.preOrderSearch(5);
        結果ノードがnullの場合
            System.out.printf ( "見つかりました。情報は番号=%d、名前=%s\nです" 、resultNode.getNo()、resultNode.getName());
            System.out.println ( "トラバーサル数:" + HeroNode.preCount);
        }それ以外{
            System.out.println ( "見つかりません" );
        } 
 
        // 順序通りのトラバーサル検索
        System.out.println ( "インオーダートラバーサル検索~~" );
        ヒーローノード resultNode1 = binaryTree.infixOrderSearch(5);
        （resultNode1 != null ）の場合 {
            System.out.printf ( "見つかりました。情報は番号=%d、名前=%s\nです" 、resultNode1.getNo()、resultNode1.getName());
            System.out.println ( "トラバーサル数:" + HeroNode.infoxCount);
        }それ以外{
            System.out.println ( "見つかりません" );
        } 
 
        // 後順トラバーサル検索
        System.out.println ( "後順トラバーサル検索~~" );
        HeroNode の結果ノード2 = binaryTree.postOrderSearch(5);
        （resultNode2がnullの場合）{
            System.out.printf ( "見つかりました。情報は番号=%d、名前=%s\nです" 、resultNode2.getNo()、resultNode2.getName());
            System.out.println ( "トラバーサル数:" + HeroNode.postCount);
        }それ以外{
            System.out.println ( "見つかりません" );
        } 
 
        System.out.println ( "ノード3を削除します" );
        バイナリツリー.delNo(3);
        System.out.println ( "削除後のノード" );
        バイナリツリーの事前順序付け();
        /**
         * 事前注文トラバーサル
         * HeroNode{番号=1、名前=Song Jiang}
         * HeroNode{番号=2、名前=Wu Yong}
         * HeroNode{番号=3、名前=Lu Junyi}
         * HeroNode{番号=5、名前=Guan Sheng}
         * HeroNode{番号=4、名前=Lin Chong}
         * 順序通りの走査
         * HeroNode{番号=2、名前=Wu Yong}
         * HeroNode{番号=1、名前=Song Jiang}
         * HeroNode{番号=5、名前=Guan Sheng}
         * HeroNode{番号=3、名前=Lu Junyi}
         * HeroNode{番号=4、名前=Lin Chong}
         * その後のトラバース
         * HeroNode{番号=2、名前=Wu Yong}
         * HeroNode{番号=5、名前=Guan Sheng}
         * HeroNode{番号=4、名前=Lin Chong}
         * HeroNode{番号=3、名前=Lu Junyi}
         * HeroNode{番号=1、名前=Song Jiang}
         * 事前注文トラバーサル検索~~
         * 見つかりました、情報番号=5、名前= Guan Sheng
         * トラバース回数: 4
         * 順序探索検索~~
         * 見つかりました、情報番号=5、名前= Guan Sheng
         * トラバース回数: 3
         * 後順トラバーサル検索~~
         * 見つかりました、情報番号=5、名前= Guan Sheng
         * トラバース回数: 2
         * ノード3を削除
         * 削除後のノード
         * HeroNode{番号=1、名前=Song Jiang}
         * HeroNode{番号=2、名前=Wu Yong}
         */
    }
 } 
 
クラス BinaryTree {
    プライベート HeroNode ルート; 
 
パブリックvoid setRoot(HeroNode ルート) {
        ルート
    } 
 
    // 事前順序トラバーサル
パブリックボイドpreOrder() {
        this.root != null の場合{
            this.root.preOrder();
        }
    } 
 
    // 順序通りの走査
パブリックvoid infixOrder() {
        this.root != null の場合{
            this.root.infixOrder();
        }
    } 
 
    //ノードを削除する
パブリックvoid delNo( int  いいえ） {
        this.root != null の場合{
            if (this.root.getNo() == no ) {
                this.root = null ;
            }それ以外{
                this.root.delNo(いいえ);
            }
        }
戻る;
    } 
 
    //後順トラバーサル
パブリックボイドpostOrder() {
        this.root != null の場合{
            this.root.postOrder();
        }
    } 
 
    // 先行順序トラバーサル検索
パブリックHeroNode preOrderSearch( int  いいえ） {
        ルートがnullの場合
root.preOrderSearch( no )を返します。
        }それ以外{
戻る ヌル;
        }
    } 
 
    // 順序通りのトラバーサル検索
パブリックHeroNode infixOrderSearch( int  いいえ） {
        ルートがnullの場合
root.infixOrderSearch( no );を返します。
        }それ以外{
戻る ヌル;
        }
    } 
 
    // 後順トラバーサル検索
パブリックHeroNode postOrderSearch( int  いいえ） {
        ルートがnullの場合
root.postOrderSearch( no )を返します。
        }それ以外{
戻る ヌル;
        }
    }
 } 
 
クラスHeroNode {
静的 プリカウント = 0;
静的  int インフォックスカウント = 0;
静的 投稿数= 0; 
 
    プライベートint  いいえ;
    プライベート文字列名;
    プライベートHeroNodeが残りました;
    プライベートHeroNode右; 
 
パブリックHeroNode( int  いいえ、文字列名）{
        this.no =いいえ;
        this.name =名前;
    } 
 
公共 整数getNo() {
戻る いいえ;
    } 
 
パブリックボイドsetNo( int  いいえ） {
        this.no =いいえ;
    } 
 
パブリック文字列getName() {
戻る 名前;
    } 
 
パブリックvoid setName(文字列名) {
        this.name =名前;
    } 
 
パブリックHeroNode getLeft() {
戻る 左;
    } 
 
パブリックvoid setLeft(HeroNode left ) {
        this.left =左;
    } 
 
パブリックHeroNode getRight() {
戻る 右;
    } 
 
パブリックvoid setRight(HeroNode右) {
        this.right =右;
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ヒーローノード{" +
 「いいえ=」 +いいえ+
 ", 名前=" +名前+
 '}' ;
    } 
 
    // 事前順序トラバーサル
パブリックボイドpreOrder() {
        System.out.println (これ) ;
        // 左のサブツリーを前順序で再帰的に走査する
        if ( this.left != null ) {
            this.left.preOrder ();
        } 
 
        // 右のサブツリーを前順序で再帰的に走査する
        if ( this.right != null ) {
            this.right .preOrder();
        }
    } 
 
    // 順序通りの走査
パブリックvoid infixOrder() {
        //左のサブツリーを順番に再帰的に走査する
        if ( this.left != null ) {
            this.left .infixOrder();
        }
        System.out.println (これ) ;
        //右のサブツリーを順番に再帰的に走査する
        if ( this.right != null ) {
            this.right .infixOrder();
        }
    } 
 
    //後順走査
パブリックボイドpostOrder() {
        // 左のサブツリーを後順に再帰的に走査する
        if ( this.left != null ) {
            this.left .postOrder();
        }
        // 右のサブツリーを後順で再帰的に走査する
        if ( this.right != null ) {
            this.right .postOrder();
        }
        System.out.println (これ) ;
    } 
 
    // ノードを再帰的に削除する
    //1. 削除するノードがリーフノードの場合は、そのノードを削除します。
    //2. 削除されたノードが非リーフノードの場合は、ツリーを削除します。
パブリックvoid delNo( int  いいえ） {
        /**
         * 1. バイナリ ツリーは一方向であるため、現在のノードの子ノードが削除する必要があるノードであるかどうかを判断できますが、現在のノードが削除する必要があるノードであるかどうかを判断することはできません。
         * 2. 現在のノードの左の子が空でなく、左の子が削除対象のノードである場合は、 this.left = null ; を設定して戻ります (再帰を終了)。
         * 3. 現在のノードの右の子が空でなく、右の子が削除対象のノードである場合は、 this.right = null ; を設定して戻ります (再帰を終了)。
         * 4. 手順 2 と 3 でノードが削除されない場合、左のサブツリーに対して再帰的な削除が実行されます。
         * 5. 手順 4 でノードが削除されなかった場合は、右側のサブツリーに対して再帰的な削除を実行する必要があります。
         */
        if ( this.left != null && this.left . no == no ) {
            this.left = null ;
戻る;
        } 
 
        this.right != null && this.right . no == noの場合{
            this.right = null ;
戻る;
        } 
 
        if ( this.left != null ) {
            this.left.delNo (いいえ) ;
        } 
 
        if ( this.right != null ) {
            this.right .delNo(いいえ);
        } 
 
    } 
 
    // 先行順序トラバーサル検索
パブリックHeroNode preOrderSearch( int  いいえ） { 
 
        HeroNode res = null ; 
 
        preCount++; //実際の比較を実行するには、 this.no == no の判定の前にこれを配置する必要があります。
        //見つかった場合は返す
        if ( this.no == no ) {
これを返します。
        }
        //見つからない場合は、左のサブツリーを再帰的に検索して先行順序を検索します
        if ( this.left != null ) {
            res = this.left.preOrderSearch ( no );
        }
        // res の場合! = nullは直接返されます
        （res != null ）の場合{
 resを返します。
        }
        //左のサブツリーが見つからない場合は、右のサブツリーに対して事前順序検索を実行します
        if ( this.right != null ) {
            res = this.right.preOrderSearch ( no );
        }
        // 見つかった場合は返す
        （res != null ）の場合{
 resを返します。
        }
 resを返します。
    } 
 
    // 順序通りのトラバーサル検索
パブリックHeroNode infixOrderSearch( int  いいえ） { 
 
        HeroNode res = null ;
        if ( this.left != null ) {
            res = this.left.infixOrderSearch (いいえ);
        }
        （res != null ）の場合{
 resを返します。
        }
        infoxCount++; //実際の比較を実行するには、 this.no == no の判定の前にこれを配置する必要があります。
        if ( this.no == no ) {
これを返します。
        }
        if ( this.right != null ) {
            res = this.right.infixOrderSearch (いいえ);
        }
        （res != null ）の場合{
 resを返します。
        }
 resを返します。
    } 
 
    // 後順トラバーサル検索
パブリックHeroNode postOrderSearch( int  いいえ） { 
 
        HeroNode res = null ;
        if ( this.left != null ) {
            res = this.left.postOrderSearch ( no );
        }
        （res != null ）の場合{
 resを返します。
        } 
 
        if ( this.right != null ) {
            res = this.right.postOrderSearch (いいえ);
        }
        （res != null ）の場合{
 resを返します。
        }
        postCount++; //実際の比較を実行するには、 this.no == no の判定の前にこれを配置する必要があります
        if ( this.no == no ) {
これを返します。
        }
 resを返します。
    }
 }

【編集者のおすすめ】

1. K8S の基本的なアーキテクチャ概念とネットワーク モデルを理解するのに役立つ 5 分
2. 1992 年に Baidu のプログラマーが逮捕されたことは、私たちにどのような警告を与えているのでしょうか。
3. オープンソースのクラウドディスクツール: Nextcloud 21 プライベートクラウドディスク構築
4. よりクリーンなMicrosoft Windows 10 21H2メジャーアップデートにより、システム内の肥大化したソフトウェアの数が削減されます
5. 996 作業システムは良いのか悪いのか?