ホームページ  >  記事  >  二分木には基本的な形式がいくつありますか?

二分木には基本的な形式がいくつありますか?

烟雨青岚
烟雨青岚オリジナル
2020-06-29 09:17:0725102ブラウズ

バイナリ ツリーには 5 つの基本的な形式があります: 1. 空のバイナリ ツリー、2. ルート ノードが 1 つだけあるバイナリ ツリー、3. 左のサブツリーのみ、4. 右のサブツリーのみ、5. 完全なバイナリ ツリー。

二分木には基本的な形式がいくつありますか?

バイナリ ツリーには 5 つの基本的な形式があります

1) 空のバイナリ ツリー: 空のツリー;

2) ルート ノードが 1 つだけあるバイナリ ツリー: ルート、つまり単一ノードだけを持つツリー;

3) 左サブツリーのみ: ルートと左サブツリー;

4) 右サブツリーのみ: ルートがあり、右サブツリーがあります;

5) 完全なバイナリ ツリー: ルートがあり、左サブツリーと右サブツリーがあります。

特別なタイプ:

1. 完全なバイナリ ツリー: バイナリ ツリーに次数 0 のノードと次数 2 のノードのみがあり、次数が 0 の場合が同じレベルにある場合、バイナリ ツリーは完全なバイナリ ツリーです。

2. 完全なバイナリ ツリー: 各ノードが深さ k および n のノードを持つ完全なバイナリ ツリーに関連している場合に限り、深さ k および n のノードを持つバイナリ ツリー。 n 個のノードが 1 対 1 に対応するとき、それは完全二分木と呼ばれます。

完全な二分木の特徴は、葉ノードが最大の順序を持​​つ 2 つのレベルにのみ表示され、ノードの左の枝の下にある子孫の最大順序が子孫の最大順序に等しいことです。右の分岐の下にある、または 1 より大きい。

バイナリ ツリーは、重要なタイプのツリー構造です。多くの現実的な問題から抽象化されたデータ構造は二分木の形式であることが多く、通常の木であっても二分木への変換は容易であり、また二分木の記憶構造やアルゴリズムは比較的単純であるため、二分木は特に重要である。二分木の特徴は、各ノードが最大 2 つの部分木しか持てず、左右の部分木に分割できることです。

バイナリ ツリーは、n 個の有限要素のセットです。このセットは空であるか、ルートと呼ばれる 1 つの要素と、それぞれ左サブツリーおよび右サブツリーと呼ばれる 2 つの互いに素な要素で構成されています。二分木であり、順序付き木です。集合が空の場合、二分木は空二分木と呼ばれます。バイナリ ツリーでは、要素はノードとも呼ばれます。

関連知識の詳細については、PHP 中国語 Web サイトをご覧ください。 !

以上が二分木には基本的な形式がいくつありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。