技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

この記事では、バイナリ ツリーについてさらに学ぶために、ツリーとバイナリ ツリーに関連する概念から始めます。

🌈个人主页：それはウェイターです
🌈C语言笔记专栏：C言語のメモ
🌈C++笔记专栏： C++ のメモ
🌈初阶数据结构笔记专栏： 基本的なデータ構造に関する注意事項

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. ツリーの概念と構造

ツリーは非線形データ構造であり、次のもので構成されます。n(n>=0)限られたノードが階層関係を持った集合を形成しますが、ツリーは実際にはほとんど価値がありませんが、二分木の方がより実用的な価値があります (この集合がツリーと呼ばれる理由は、根が上を向き、葉が付いているためです)。下を向くとまるで木のように見えます）

• ルート ノードと呼ばれる特別なノードがあり、ルート ノードには先行ノードがありません。
• ルートノードを除いた残りのノードは次のように分割されます。M(M>0)素集合T1、T2、....、Tmの各セットTi(1<=i<=m)これは、ツリーと同様の構造を持つ別のサブツリーです。各サブツリーのルート ノードには 1 つのみの先行ノードがあり、0 個以上の後続ノードを持つことができます。
• ツリーは再帰的に定義されますが、同時に注意が必要です。ツリー構造でサブツリー間に交差があってはなりません。交差しないとツリー構造になりません。

1.1 ツリーの関連概念

• ノードの次数: 上の図に示すように、ノードに含まれるサブツリーの数はノードの次数と呼ばれます。A は 6 です。
• リーフノードまたはターミナルノード: 次数 0 のノードはリーフ ノードと呼ばれます。 上の図に示すように: B、C、H、I... などのノードはリーフ ノードです。
• 非終端ノードまたはブランチノード：次数が 0 でないノード 上図に示すように、D、E、F、G... などのノードが分岐ノードです。
• 親ノードまたは親ノード: ノードに子ノードが含まれる場合、このノードはその子ノードの親ノードと呼ばれます。上の図に示すように、A は B の親ノードです。
• 子ノードまたは子ノード: ノードに含まれるサブツリーのルート ノードは、ノードの子ノードと呼ばれます。 上の図に示すように、B は A の子ノードです。
• 兄弟ノード: 同じ親ノードを持つノードは兄弟ノードと呼ばれます。上に示すように、B と C は兄弟ノードです。
• 木の程度: ツリーでは、上に示すように、最大​​のノードの次数がツリーの次数と呼ばれます。ツリーの次数は 6 です。
• ノードレベル: ルートの定義から開始すると、ルートは第 1 レベル、ルートの子ノードは第 2 レベル、というようになります。
• 木の高さまたは深さ: ツリー内のノードの最大レベル (上に示す): ツリーの高さは 4 です。
• いとこノード: 上の図に示すように、親が同じレベルにあるノードは互いにいとこです。H と I は互いに兄弟ノードです。
• ノードの祖先: 上の図に示すように、ルートからノードまでの分岐上のすべてのノード: A はすべてのノードの祖先です。
• 子孫 : 特定のノードをルートとするサブツリー内のノードは、そのノードの子孫と呼ばれます。上に示すように、すべてのノードは A の子孫です。
• 森: m (m>0) 個の互いに素なツリーの集合をフォレストと呼びます。

2. ツリーのストレージ表現

木構造は線形テーブルに比べて複雑なため、値の範囲とノード間の関係の両方を保存する必要があります。

これまでの知識に基づいたいくつかの方法を次に示します。

• それぞれの子にはアドレスがあり、ポインター配列を介してデータを保存できます (スペースは固定されており、新しいスペースを申請する際にはコストとスペースの問題が発生します)。
• 最初の方法の最適化では、ポインタ配列を子を格納するシーケンス テーブルとして使用し、固定領域の問題を解決します。
• 一般的に推奨される解決策: 左子、右兄弟方式 (長兄が 2 人目を引き、次子が 3 人目を引き取るため、両親が疲れる必要はありません)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

もちろん、上記の方法に限定されるものではなく、親式、子式、子親式、子兄弟式等もある。ここでは、最も一般的に使用されるものを簡単に説明します子供の兄弟の代表

3. 二分木の概念

バイナリ ツリーはノードの有限セットです。このセットには次の 2 つの状況が考えられます。

1. 空の木
2. これは、ルート ノードと、左サブツリーと右サブツリーと呼ばれる 2 つのバイナリ ツリーで構成されます (サブツリーは空のツリーの場合もあります)。

この図から 2 つの結論が導き出されます:

1. 二分木には次数が 2 より大きいノードはありません

2. 二分木の部分木は左右の部分木に分割でき、順序を逆にすることはできないため、二分木は順序付き木となります。

知らせ: どのバイナリ ツリーでも、次の状況で構成されます (空の木の状況は最も忘れられやすい)

3.1 実際の二分木（見るたびに何度かお辞儀をする必要がある）

4. 特殊な二分木

• 完全なバイナリツリー : 各層のノード数が最大に達した場合、バイナリ ツリーは完全なバイナリ ツリーになります。つまり、二分木のレベルは K で、ノードの総数は 2 です。^け-1 の場合、完全なバイナリ ツリーになります。
• 完全な二分木 : 完全なバイナリ ツリーは非常に効率的なデータ構造です。完全なバイナリ ツリーは完全なバイナリ ツリーから派生します。高さ K でノードが n の二分木について、各ノードが高さ K の完全な二分木内の 1 から n までの番号が付けられたノードと 1 対 1 に対応する場合に限り、完全な二分木と呼ばれます。

簡単にまとめると:

• 完全なバイナリ ツリーのすべてのレベルがいっぱいです

• 完全な二分木の高さが n の場合、最初の n-1 レベルはいっぱいですが、最後のレベルはいっぱいではない可能性があります。ただし、左から右に連続している必要があります

• 完全なバイナリ ツリーは非常に効率的なデータ構造であり、完全なバイナリ ツリーは特殊なタイプの完全なバイナリ ツリーです。

• 完全なバイナリ ツリーは、完全なバイナリ ツリーの必要十分条件です。

4.1 完全な二分木に属さない状況

これは通常の二分木であり、左から右へ連続していません。

5. バイナリツリーの記憶構造

バイナリ ツリーは通常、2 つの構造で格納できます。1 つはシーケンシャル構造、もう 1 つはチェーン構造です。

5.1 シーケンシャルストレージ

シーケンシャル構造ストレージは配列を使用して格納することですが、一般に、配列は完全なバイナリ ツリーを表す場合にのみ適しています。バイナリ ツリーがいっぱいでない場合、実際にはヒープのみがストレージに配列を使用するため、スペースが無駄になります。バイナリ ツリーの逐次ストレージは物理的には配列であり、論理的にはバイナリ ツリーです。次の質問を解くには、物理​​的な配列と論理的なバイナリ ツリーの組み合わせを使用する必要があります。

5.2 親ノードと子ノード間の通常の添え字関係 (重要)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(左右の子の区別はありません)

• ３点目については個人的な推論ですが、leftchild添え字は次のように分割されますleftchild- 1そして1、のためにleftchild-1のためにparent下付き文字を 2 回付けます。(child - 1) / 2オペレーターは、leftchildとして取り出します1部分的に 2 で割った整数は 0、leftchild -1その一部は次のように見ることができますleftchild、そしてrightchild与leftchild相差1、なぜならrightchild = leftchild - 1そして上を通してleftchild - 1 ~= leftchild、と推測できます。rightchild = leftchild(在进行/2运算，取整数情况下)

5.3 チェーンストレージ

バイナリ ツリーのリンクされたストレージ構造とは、リンク リストを使用してバイナリ ツリーを表現すること、つまり、チェーンを使用して要素の論理関係を示すことを指します。 通常の方法では、リンク リストの各ノードは、データ フィールドと左右のポインタ フィールドという 3 つのフィールドで構成されます。左右のポインタは、左の子と右の子が指すリンクのストレージ アドレスを指定するために使用されます。ノードのそれぞれが配置されます。連鎖構造は 2 進連鎖と 3 分岐連鎖に分けられます。現在、私たちの研究では一般に 2 進連鎖が使用されます。その後、赤黒ツリーなどの高次のデータ構造を学習する場合には、3 分岐連鎖が使用されます。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 概要

シーケンシャル構造のストレージは配列を介して保存されます。一般に、配列は完全なバイナリ ツリーにのみ適しています。不完全なバイナリ ツリーは、配列構造のストレージには適していません。 。しかし実際には、配列はヒープが使用される場合にのみストレージとして使用され、そのほとんどはチェーン構造を介して保存されます。

その理由は:

1. まず第一に、バイナリ ツリーは他のデータ構造とは異なり、多くのスペースとロジックを消費するため、ヒープ データの追加、削除、確認、変更に適した独自の論理構造を持っていることを知っておく必要があります。はより複雑です。このような複雑な構造をデータの保存に使用すると、大きな価値が生まれます。の場合は、最初からシーケンシャルテーブルを使用してデータを格納する方が良いでしょう。同時に、一般的に言えば、バイナリツリーの構造は再帰的であり、それを非再帰的に実装することはより困難です。
2. 通常のバイナリ ツリーの記憶要素の密度は非常に低い場合があり、連続的な記憶構造により多くのスペースが無駄になります。
3. ヒープは、ツリー内のノードの位置を決定する「ヒープ属性」に従ってソートされます (以下のヒープの概要で説明します)。

---

以上がこの記事の内容です、読んでいただいた皆様、ありがとうございました！基本データ構造に関する Dian Xiaoer のメモが、基本データ構造の学習に役立つことを願っています。