構造とアルゴリズム: バイナリツリーとマルチツリー

1. ツリー構造

1. 配列とリンクリスト

配列構造

配列ストレージは、要素に添字でアクセスするため、クエリ速度が速くなります。配列要素が順序付けられている場合は、バイナリ検索を使用して検索速度を上げることができます。新しい要素を追加すると複数の添字が移動する可能性がある場合は、効率が低くなります。

リンクリスト構造

リンクリストは要素を格納し、要素の追加や削除には効率的ですが、要素をトラバースするには毎回先頭ノードから開始する必要があり、非常に非効率的です。

ツリー構造により、データの保存と読み取りの効率が比較的向上します。

2. ツリー構造の概念

ルートノード: ツリーのルート、つまり親ノードのないノード (上図のノード A など)。
兄弟ノード: 同じ親ノードを持つ子ノード。図の点 B と C に示すように、
リーフノード: 子ノードを持たないノード。図に示すように、DEFG ノード。
木の高さ: 最大層数。図に示すように、3 層あります。
パス: ルートノードから指定されたノードへのルートを検索します。

ツリー構造はネストされた構造です。ツリー構造の外側の層と内側の層は同様の構造を持つため、この構造は多くの場合再帰的に表現できます。従来のデータ構造におけるさまざまなツリー図は、典型的なツリー構造です。ツリーは、ルート、左サブツリー、右サブツリーとして単純に表すことができます。左のサブツリーと右のサブツリーにはそれぞれ独自のサブツリーがあります。

2. 二分木モデル

木には多くの種類があります。二分木は重要な種類の木構造です。各ノードが最大 2 つの子ノードを持つことができる形式は、二分木と呼ばれます。二分木の子ノードは、左ノードと右ノードに分かれています。多くの実用的な問題から抽象化されたデータ構造は、多くの場合、二分木の形式になっています。

完全な二分木

バイナリツリーのすべてのリーフノードは、最後のレイヤーまたは最後から 2 番目のレイヤーにあり、最後のレイヤーのリーフノードは左側で連続しており、最後から 2 番目のレイヤーのリーフノードは右側で連続しています。これを完全バイナリツリーと呼びます。

完全な二分木

バイナリツリーのすべてのリーフノードが最後のレイヤーにあり、ノードの総数が 2^n -1 (n はレイヤーの数) の場合、そのツリーは完全バイナリツリーと呼ばれます。

バランスのとれた二分木

バランスのとれた二分木とは、任意のノードのサブツリーの高さの差の絶対値が 1 以下であり、左右のサブツリーが両方ともバランスのとれた二分木であることを意味します。一般的なバランスのとれた木には、B ツリー (多方向バランス探索木)、AVL ツリー (二分バランス探索木) などがあります。

二分探索木

二分探索木 (BinarySearchTree) は二分木であるだけでなく、特定の順序も満たします。つまり、ノードの左の子はそれ自体よりも小さく、ノードの右の子はそれ自体よりも大きくなります。

3. バイナリツリーエンコーディング

1. 基本コード

ノードコード

クラス TreeNode {
    プライベート文字列 num ;
    プライベート TreeNode leftNode;
    プライベート TreeNode rightNode ;
パブリックTreeNode(文字列 num) {
        this.num = num;
    } @オーバーライド
パブリック文字列toString() {
戻る  "TreeNode{num=" + num + '}' ;
    }}

ツリー構造コード

クラス BinaryTree01 {
    プライベート TreeNode ルート;
 }

2. トラバーサルと検索

事前順序トラバーサル検索

まず現在のノードのデータを処理し、次に左のサブツリーと右のサブツリーを順番に再帰的にトラバースします。

パブリックvoid prevTraverse() {
    // 親ノードを出力する
    System.out.println (これ) ;
    // 左のサブツリーを前順に再帰的に走査する
    if (this.leftNode != null ) {
        this.leftNode.prevTraverse();
    } // 右のサブツリーを前順序で再帰的に走査する
    if (this.rightNode != null ) {
        this.rightNode.prevTraverse();
    }} public TreeNode prevSearch(String num) { //現在のノードを比較する
    if (this.num.equals(num)) {
これを返します。
    } // 左のサブツリーを再帰的に走査して検索する
    ツリーノード findNode = null ;
    if (this.leftNode != null ) {
        findNode = this.leftNode.prevSearch(num);
    } // 左サブツリーのトラバーサルヒット
    findNode がnullの場合
findNodeを返します。
    } // 右のサブツリーを再帰的に走査して検索する
    if (this.rightNode != null ) {
        findNode = this.rightNode.prevSearch(num);
    } findNodeを返します。
 }

順序探索検索

まず左のサブツリーを再帰的に走査し、次に親ノードを処理し、次に右のサブツリーを再帰的に走査します。

パブリックボイドmidTraverse() {
    // 左のサブツリーを再帰的に走査する
    if (this.leftNode != null ) {
        this.leftNode.midTraverse();
    } // 親ノードを出力する
    System.out.println (これ) ;
    // 右のサブツリーを再帰的に走査する
    if (this.rightNode != null ) {
        this.rightNode.midTraverse();
    }} public TreeNode midSearch(String num) { // 左のサブツリーを再帰的に走査して検索する
    ツリーノード findNode = null ;
    if (this.leftNode != null ) {
        findNode = this.leftNode.midSearch(num);
    } の場合 (findNode != null ) {
 findNodeを返します。
    } // 現在のノードを比較する
    if (this.num.equals(num)) {
これを返します。
    } // 右のサブツリーを再帰的に走査して検索する
    if (this.rightNode != null ) {
        findNode = this.rightNode.midSearch(num);
    } findNodeを返します。
 }

後順序トラバーサル検索

まず左のサブツリーを再帰的にトラバースし、次に右のサブツリーを再帰的にトラバースし、最後に親ノードを処理します。

パブリックボイドlastTraverse() {
    // 左のサブツリーを後順に再帰的に走査する
    if (this.leftNode != null ) {
        this.leftNode.lastTraverse();
    } // 右のサブツリーを後順で再帰的に走査する
    if (this.rightNode != null ) {
        this.rightNode.lastTraverse();
    } // 親ノードを出力する
    System.out.println (これ) ;
 } public TreeNode lastSearch(String num) { // 左のサブツリーを再帰的に走査して検索する
    ツリーノード findNode = null ;
    if (this.leftNode != null ) {
        findNode = this.leftNode.lastSearch(num);
    } の場合 (findNode != null ) {
 findNodeを返します。
    } // 右のサブツリーを再帰的に走査して検索する
    if (this.rightNode != null ) {
        findNode = this.rightNode.lastSearch(num);
    } の場合 (findNode != null ) {
 findNodeを返します。
    } // 現在のノードを比較する
    if (this.num.equals(num)) {
これを返します。
    }戻る ヌル;
 }

3. ノードを削除する

現在削除中のノードがリーフノードである場合は、ノードを直接削除できます。削除中のノードが非リーフノードである場合は、ノードツリーが削除されます。

パブリックvoid deleteNode(文字列 num) {
    // 左のノードが削除されているかどうかを判定する
    this.leftNode != null && this.leftNode.num.equals(num) の場合 {
        this.leftNode = null ;
戻る;
    } // 正しいノードが削除されているかどうかを判定する
    this.rightNode != null && this.rightNode.num.equals(num) の場合 {
        this.rightNode = null ;
戻る;
    } // 左のサブツリーを走査し、再帰的に削除する
    if (this.leftNode != null ) {
        this.leftNode.deleteNode(num);
    } // 右のサブツリーを走査し、再帰的に削除する
    if (this.rightNode != null ) {
        右ノードからノード番号を削除します。
    }}