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

基本概念

データストレージの観点から見ると、配列ストレージとツリーストレージは相互に変換できます。つまり、配列をツリーに変換したり、ツリーを配列に変換したりできます。次の図に示すように:

順次記憶バイナリツリーの特性:

順次ストレージでは通常、完全なバイナリツリーのみが考慮されます。
n 番目の要素の左の子ノードは 2 * n+1 です。
n 番目の要素の右の子ノードは 2 * n + 2 です。
n番目の要素の親ノードは(n-1)/2です。
n はバイナリツリー内の要素数を表します (上の図に示すように、番号は 0 から始まります)。

必要

配列{1,2,3,4,5,6,7}が与えられた場合、二分木の順序順走査の方法で走査する必要があります。順序順走査の結果は1,2,4,5,3,6,7、

さらに、インオーダートラバーサルとポストオーダートラバーサルを完了します。

コード例

パッケージ com.xie.tree; 
 
 /**
 * @著者: xiexiaofei
 * @日付: 2020-02-09 20:04
 * @説明：
 */
パブリッククラス ArrBinaryTreeDemo {
公共 静的void main(String[] args) {
 int [] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree は、arr という名前のバイナリツリーを作成します。
        System. out .println( "順番に格納されたバイナリツリーの事前順序トラバーサル配列" );
        arrBinaryTree.preOrder(0);
        System.out.println( ) ;
        System.out.println ( "バイナリツリーを順番に格納する順序走査配列" );
        バイナリツリーの順序を0に変更します。
        System.out.println( ) ;
        System. out .println( "バイナリツリーを順番に格納する後順トラバーサル配列" );
        arrBinaryTree.postOrder(0);
        System.out.println( ) ; 
 
        /**
         * バイナリツリーの事前順序走査配列を順番に格納する
         * 1 2 4 5 3 6 7
         * バイナリツリーの順序付き走査配列を順番に格納する
         * 2 4 5 1 3 6 7
         * バイナリツリーのポストオーダートラバーサル配列を順番に格納する
         * 2 4 5 3 6 7 1
         */ 
 
    }
 } 
 
 //順次ストレージバイナリツリーのトラバーサルを実装する
クラス ArrBinaryTree {
    private int [] arr; //データノードを格納する配列
 
パブリックArrBinaryTree( int [] arr) {
        this.arr = arr;
    } 
 
    /**
     * 順番に格納されたバイナリツリーの事前順序走査を完了するメソッドを記述します。
     *
     * @paramインデックス配列の添え字
     */
パブリックvoid preOrder( int  索引） {
        (arr == null || arr.length == 0)の場合{
            System.out.println ( "配列は空なので、バイナリツリーの事前順序で走査することはできません" );
        }
        // 現在の要素を出力する
        システム.out.print (arr[インデックス]+ "" );
        //左への再帰的トラバーサル
        ((2 *インデックス+ 1) < arr.length) の場合 {
            preOrder(2 *インデックス+ 1);
        }
        //右方向への再帰
        ((2 *インデックス+ 2) < arr.length) の場合 {
            preOrder(2 *インデックス+ 2);
        }
    } 
 
    /**
     * 順番に格納されたバイナリツリーの順序どおりのトラバーサルを完了するメソッドを記述します。
     *
     * @paramインデックス 
     */
パブリックvoid infixOrder( int  索引） {
        (arr == null || arr.length == 0)の場合{
            System.out.println ( "配列は空なので、バイナリツリーの事前順序で走査することはできません" );
        } 
 
        //左への再帰的トラバーサル
        ((2 *インデックス+ 1) < arr.length) の場合 {
            preOrder(2 *インデックス+ 1);
        } 
 
        // 現在の要素を出力する
        システム.out.print (arr[インデックス]+ "" ); 
 
        //右方向への再帰
        ((2 *インデックス+ 2) < arr.length) の場合 {
            preOrder(2 *インデックス+ 2);
        } 
 
    } 
 
    /**
     * 順番に格納されたバイナリツリーの事後順序トラバーサルを完了するメソッドを記述します。
     *
     * @paramインデックス 
     */
パブリックvoid postOrder( int  索引） {
        (arr == null || arr.length == 0)の場合{
            System.out.println ( "配列は空なので、バイナリツリーの事前順序で走査することはできません" );
        } 
 
        //左への再帰的トラバーサル
        ((2 *インデックス+ 1) < arr.length) の場合 {
            preOrder(2 *インデックス+ 1);
        } 
 
        //右方向への再帰
        ((2 *インデックス+ 2) < arr.length) の場合 {
            preOrder(2 *インデックス+ 2);
        } 
 
        // 現在の要素を出力する
        システム.out.print (arr[インデックス]+ "" ); 
 
    } 
 
 }