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

[[388829]]

まず質問を見てみましょう

シーケンス{1,3,6,8,10,14}を二分木に構築します。次の図に示すように、n+1=7です。

問題分析:

上記の二分木を順番に走査すると、シーケンスは{8,3,10,1,14,6}になります。
ただし、ノード 6、8、10、および 14 の左および右のポインタは完全には使用されていません。
各ノードの左と右のポインタを最大限に活用し、各ノードがその前面ノードと背面ノードを指すようにしたい場合はどうすればよいでしょうか。
ソリューション - スレッドバイナリツリー

スレッドバイナリツリーの基本的な紹介

n 個のノードのバイナリリンクリストには、n+1 [式 2n-(n-1)=n+1] 個の null ポインターフィールドが含まれます。バイナリリンクリスト内の空のポインタフィールドは、特定のトラバーサル順序でノードの前ポイントと後ポイントへのポインタを格納するために使用されます (この追加のポインタは、手がかりと呼ばれます)。
このスレッド付きのバイナリリンクリストはスレッドリンクリストと呼ばれ、対応するバイナリツリーはスレッドバイナリツリー (Threaded Binary Tree) と呼ばれます。ヒントの性質に応じて、ヒント付きバイナリツリーは、前順序ヒント付きバイナリツリー、中順序ヒント付きバイナリツリー、後順序ヒント付きバイナリツリーの 3 つのタイプに分けられます。
ノードの前のノードは先行ノードと呼ばれます。
ノードの後のノードは後続ノードと呼ばれます。

順序手がかり二分木図

順序通りの走査の結果は{8,3,10,1,14,6}です。

注: バイナリツリーがスレッド化された後、Node ノードの左と右の属性は次のようになります。

left が指す値は左のサブツリー、または指し示す先行ノードです。たとえば、ノード ① の左は左のサブツリーを指し、ノード ⑩ の左は先行ノードを指します。
right が指す右サブツリーは、後続ノードを指すこともあります。たとえば、ノード ① の右は右サブツリーを指し、ノード ⑩ の右は後続ノードを指します。

コード例

パッケージ com.xie.tree.threadedbinarytree; 
 
パブリッククラスThreadedBinaryTreeDemo {
公共 静的void main(String[] args) {
        // 順序付き手がかりバイナリツリーをテストする
        HeroNode ルート = 新しい HeroNode(1, "tom" );
        HeroNode node2 = 新しいHeroNode(3, "jack" );
        HeroNode node3 = 新しいHeroNode(6, "smith" );
        HeroNode node4 = 新しいHeroNode(8, "mary" );
        HeroNode node5 = 新しいHeroNode(10, "king" );
        HeroNode node6 = 新しいHeroNode(14, "dim" ); 
 
        ルート.setLeft(ノード2);
        ルートを右に設定します(ノード3); 
 
        ノード4を左に設定します。
        ノード2を右に設定します(ノード5); 
 
        ノード3を左に設定します(ノード6); 
 
        スレッドバイナリツリー threadedBinaryTree = 新しい ThreadedBinaryTree();
        スレッドバイナリツリー。ルートを設定します。
        スレッドバイナリツリー。 
 
        //テスト: ノード10でテスト
        HeroNode左= node5.getLeft();
        System.out.println ( "ノード10の前身ノードは:" + left );
        HeroNode右= node5.getRight();
        System.out.println ( "ノード10の後継ノードは:" + right ); 
 
        System.out.println ( "スレッドアプローチを使用してスレッドバイナリツリーをトラバースします" );
        スレッドバイナリツリー。スレッドバイナリツリーリスト(); 
 
        /**
         * ノード 10 の前身ノードは、HeroNode{ no =3, name =jack}です。
         * ノード10の後継ノードは、HeroNode{ no =1, name =tom}です。
         * スレッド化されたアプローチを使用して、スレッド化されたバイナリツリーをトラバースします。
         * HeroNode{番号=8、名前=mary}
         * HeroNode{番号=3、名前=jack}
         * HeroNode{番号=10、名前=king}
         * HeroNode{番号=1、名前=tom}
         * HeroNode{ no =14, name =dim}
         * HeroNode{番号=6、名前=smith}
         */ 
 
    }
 } 
 
 //スレッド関数を実装するバイナリツリー
クラス ThreadedBinaryTree {
    プライベート HeroNode ルート;
    //スレッド化を実現するには、現在のノードの前のノードへのポインタを作成する必要があります
    //再帰的にスレッド化する場合、pre は常に前のノードを保持します
    プライベートHeroNode pre; 
 
パブリックvoid setRoot(HeroNode ルート) {
        ルート
    } 
 
    /**
     * スレッド化されたバイナリツリーをトラバースするためのメソッド。
     */
パブリックボイドスレッドバイナリツリーリスト() {
        //ルートから現在トラバースされているノードを格納する変数を定義します
        HeroNode ノード = ルート;
        while (ノード != null ) {
            // leftType==1 のノードを探すためにループします。最初に見つかったのはノード 8 です。
            // トラバーサルが進むにつれて、次の内容が変わります。leftType==1 の場合、スレッド処理後にノードが有効なノードであることを意味します。
            (node.getLeftType() == 0) の間 {
                ノード = node.getLeft();
            }
            //現在のノードを印刷する
            System.out.println (ノード) ;
            //現在のノードの右ポインタが後続ノードを指している場合は、出力を続けます
            (node.getRightType() == 1) の間 {
                //現在のノードの後継ノードを取得します
                ノード = node.getRight();
                System.out.println (ノード) ;
            }
            // 走査したノードを置き換える
            ノード = node.getRight();
        }
    } 
 
    /**
     * threadedNodes メソッドをオーバーロードする
     */
パブリックボイドスレッドノード（）{
        スレッドノード(ルート);
    } 
 
    /**
     * バイナリツリーをスレッド化するメソッドを書く
     *
     * @param node 現在スレッド化する必要があるノード
     */
パブリックvoid threadedNodes(HeroNode ノード) {
        if (ノード == null ) {
戻る;
        } 
 
        //まず左のサブツリーをスレッドする
        スレッド化されたノード(node.getLeft());
        //現在のノードをキューする [難しい] 
 
        //現在のノードの前身ノードを処理する
        //8 ノード、8ノードとして理解します。left = null  
        （node.getLeft() == nullの場合）{
            //現在のノードの左ポインタを前のノードを指すようにします
            ノードを左に設定します(pre);
            //現在のノードの左ポインタ型を変更する
            ノードを左タイプに設定します(1);
        } 
 
        //後続ノードを処理する
        pre != null && pre.getRight() == null の場合{
            //先行ノードの右ポインタを現在のノードを指すようにします
            ノードを右に設定します。
            //先行ノードの右ポインタ型を変更する
            プレセットRightType(1);
        }
        //各ノードを処理した後、現在のノードを次のノードの前身ノードにします
        pre = ノード; 
 
        //右のサブツリーを再スレッドする
        スレッド化されたノード(node.getRight());
    } 
 
 } 
 
 //HeroNodeノードを作成
クラスHeroNode {
静的 プリカウント = 0;
静的  int インフォックスカウント = 0;
静的 投稿数= 0; 
 
    プライベートint  いいえ;
    プライベート文字列名;
    プライベートHeroNodeが残りました;
    プライベートHeroNode右; 
 
    //0 は左のサブツリーを指し、1 は前のノードを指していることを意味します
    プライベートint leftType;
    //0は右のサブツリーを指し、1は後続ノードを指していることを意味します
    プライベートint rightType; 
 
パブリック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 =右;
    } 
 
公共  int getLeftType() {
 leftTypeを返します。
    } 
 
パブリックvoid setLeftType( int leftType) {
        this.leftType = leftType;
    } 
 
公共  int getRightType() {
 rightTypeを返します。
    } 
 
パブリックvoid setRightType( int rightType ) {
        this.rightType = 右タイプ;
    } 
 
    @オーバーライド
パブリック文字列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を返します。
    }
 }