JavaScriptのデータ構造とアルゴリズムのバイナリツリーを詳しく解説_基礎知識

二分木の概念

バイナリ ツリーは、n (n>=0) 個のノードの有限集合です。この集合は、空のセット (空のバイナリ ツリー) であるか、ルート ノードと 2 つの相互に素なツリーで構成されます。ルート ノードの左側のサブツリーと右側のサブツリーで構成されます。

二分木の特徴

各ノードには最大 2 つのサブツリーがあるため、バイナリ ツリーには次数が 2 を超えるノードはありません。バイナリ ツリーの各ノードはオブジェクトであり、各データ ノードには 3 つのポインタがあります。これらのポインタは、親、左の子、右の子へのポインタです。各ノードはポインタを介して相互に接続されます。接続されたポインタ間の関係は親子関係です。

二分木ノードの定義

二分木のノードは次のように定義されます:

コードをコピー コードは次のとおりです:

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

二分木の 5 つの基本形式

空のバイナリツリー
ルートノードは 1 つだけです
ルートノードには左側のサブツリーのみがあります
ルートノードには正しいサブツリーのみがあります
ルートノードには左と右の両方のサブツリーがあります

3 つのノードを持つ通常のツリーには、2 層または 3 層の 2 つの状況しかありません。ただし、二分木は左右を区別する必要があるため、次の 5 つの形式に進化します。

特殊バイナリツリー

斜めの木

上の最後の写真の2枚目と3枚目にあるように。

完全なバイナリ ツリー

二分木で、すべての分岐ノードに左部分木と右部分木があり、すべての葉が同じレベルにある場合、そのような二分木は完全二分木と呼ばれます。以下に示すように:

完全なバイナリツリー

完全なバイナリ ツリーとは、最後のレベルの左側がいっぱいで、右側がいっぱいかどうかにかかわらず、残りのレベルがいっぱいであることを意味します。深さが k でノード数が 2^k - 1 の二分木は、完全な二分木 (完全な二分木) です。深さ k で隙間のない木です。

完全なバイナリツリーの特徴は次のとおりです:

リーフ ノードは、下の 2 つのレベルにのみ表示されます。

一番下の葉は左側の連続位置に集中する必要があります。

最後から 2 番目の層に葉ノードがある場合、それらは右側の連続した位置になければなりません。

ノードの次数が 1 の場合、ノードには子だけが残っています。

同じノード ツリーを持つバイナリ ツリー、完全なバイナリ ツリーの深さは最も浅くなります。

注: 完全なバイナリ ツリーは完全なバイナリ ツリーである必要がありますが、完全なバイナリ ツリーは必ずしも完全なバイナリ ツリーである必要はありません。

アルゴリズムは次のとおりです:

コードをコピーします コードは次のとおりです:

bool is_complete(tree *root)
{
キューq; ツリー *ptr;
// 幅優先走査 (レベル走査) を実行し、NULL ノードをキューに入れます
q.push(ルート); While ((ptr = q.pop()) != NULL)
{
q.push(ptr->left);
q.push(ptr->right);
}

// 未訪問のノードがあるかどうかを判断します
(!q.is_empty()) {

ptr = q.pop();
// 未訪問の非 NULL ノードがある場合、ツリーには穴があり、不完全なバイナリ ツリーになります
If (NULL != ptr)
                                                                                   false を返す;                                                                                                               }

true を返します。
}

二分木のプロパティ

二分木のプロパティ 1: 二分木の i 番目のレベルには最大 2^(i-1) 個のノード (i>=1) があります

二分木の性質 2: 深さ k の二分木には最大 2^k-1 個のノード (k>=1) が含まれます

二分木の逐次記憶構造

バイナリ ツリーのシーケンシャル ストレージ構造では、1 次元配列を使用してバイナリ ツリー内の各ノードを格納し、ノードの格納場所はノード間の論理関係を反映できます。

バイナリリンクリスト

順次ストレージの適用性は強くないため、チェーンストレージ構造を考慮する必要があります。国際的な慣例によれば、バイナリ ツリーの保存には通常、チェーン ストレージ構造が使用されます。

バイナリ ツリーの各ノードには最大でも 2 つの子があるため、データ フィールドとそのための 2 つのポインタ フィールドを設計するのは自然な考え方です。このようなリンク リストをバイナリ リンク リストと呼びます。

バイナリツリートラバーサル

バイナリ ツリーのトラバースとは、ルート ノードから開始してバイナリ ツリー内のすべてのノードを特定の順序で訪問し、各ノードが 1 回だけ訪問されるようにすることを意味します。

バイナリ ツリーをトラバースするには、次の 3 つの方法があります。

(1) 事前順序トラバーサル (DLR)。最初にルート ノードにアクセスし、次に左のサブツリーをトラバースし、最後に右のサブツリーをトラバースします。ルート-左-右の略語。

(2) 順序トラバーサル (LDR)。最初に左側のサブツリーをトラバースし、次にルート ノードにアクセスし、最後に右側のサブツリーをトラバースします。左ルート右と略されます。

(3) ポストオーダートラバーサル (LRD)。最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルート ノードにアクセスします。左-右-ルートと略されます。

事前注文トラバーサル:

バイナリ ツリーが空の場合、操作は返されません。それ以外の場合は、ルート ノードが最初にアクセスされ、次に左のサブツリーが事前順序で走査され、次に右のサブツリーが事前順序で走査されます。

走査の順序は次のとおりです: A B D H I E J C F K G

コードをコピー コードは次のとおりです:

// 事前注文トラバーサル
関数 preOrder(node){
If(!node == null){
putstr(node.show() " ");
preOrder(node.left);
preOrder(node.right);
}
}

順序トラバーサル:

ツリーが空の場合、操作は返されません。それ以外の場合は、ルート ノードから開始して (ルート ノードが最初に訪問されないことに注意してください)、ルート ノードの左側のサブツリーを順番にたどってから、ルート ノードにアクセスします。最後に、正しいサブツリーを順番にたどります。

走査の順序は次のとおりです: H D I B E J A F K C G

コードをコピー コードは次のとおりです:

//再帰を使用して順序内トラバーサルを実装します
関数 inOrder(node){
If(!(node==null)){
inOrder(node.left);//最初に左側のサブツリーにアクセスします
putstr(node.show() " ");//ルートノードに再度アクセスします
inOrder(node.right);//右サブツリーへの最終アクセス
}
}

事後トラバーサル:

ツリーが空の場合は、何もしない操作が戻ります。それ以外の場合は、左右のサブツリーが左から右に、最初にリーフ、次にノードと走査され、最後にルート ノードが参照されます。

走査の順序は次のとおりです: H I D J E B K F G C A

コードをコピー コードは次のとおりです:

//ポストオーダートラバーサル
関数 postOrder(node){
If(!node == null){
PostOrder(node.left);
postOrder(node.right);
putStr(node.show() " ");
}
}

二分探索木の実装

二分探索木 (BST) はノードで構成されているため、次のように Node ノード オブジェクトを定義します。

コードをコピー コードは次のとおりです:

関数 Node(data,left,right){
This.data = データ;
This.left = left;// 左側のノードのリンクを保存します
This.right = right;
This.show = show;
}

関数 show(){
Return this.data;//ノードに保存されているデータを表示
}

最大値と最小値を求める

BST の最小値と最大値を見つけるのは、小さい値が常に左側の子ノードにあるため、非常に簡単です。BST の最小値を見つけるには、最後のノードが見つかるまで左側のサブツリーをたどるだけです。

最小値を求める

コードをコピーします コードは次のとおりです:

関数 getMin(){
var current = this.root;
While(!(current.left == null)){
現在 = current.left;
}
current.data を返します;
}

このメソッドは、BST の左端のノードに到達するまで、BST の左のサブツリーを 1 つずつ走査します。このノードは次のように定義されます。

コードをコピー コードは次のとおりです:

current.left = null;

このとき、現在のノードに保存されている値は最小値です

最大値を求める

BST の最大値を見つけるには、最後のノードが見つかるまで右のサブツリーをたどるだけで済み、このノードに保存されている値が最大値になります。

コードをコピー コードは次のとおりです:

関数 getMax(){
var current = this.root;
While(!(current.right == null)){
current = current.right;
}
current.data を返します;
}