バイナリ ツリーは、ノードが最大 2 つの子を持つことができることを意味します。ここでは、バイナリ名自体が「2」を示唆しています。したがって、各ノードは 0、1、または 2 つの子を持つことができます。

Java if else ステートメント

例を通して二分木を理解しましょう。

各ノードには最大 2 つの子が含まれるため、上記のツリーはバイナリ ツリーです。上記のツリーの論理表現は次のとおりです。

上記のツリーでは、ノード 1 に 2 つのポインタ、つまり、それぞれ左ノードと右ノードを指す左ポインタと右ポインタが含まれています。ノード 2 には両方のノード (左ノードと右ノード) が含まれます。したがって、2 つのポインター (左と右) があります。ノード 3、5、および 6 はリーフ ノードであるため、これらすべてのノードには次のものが含まれます。 ヌル 左右両方の部分にポインターが表示されます。

二分木の性質

• i の各レベルでのノードの最大数は 2 です^私。
• ツリーの高さは、ルート ノードからリーフ ノードまでの最長パスとして定義されます。上に示したツリーの高さは 3 です。したがって、高さ 3 でのノードの最大数は、(1+2+4+8) = 15 に等しくなります。一般に、高さ h で可能なノードの最大数は、は(2⁰+2¹+2²+….2^h) = 2^h+1-1.
• 高さ h で可能なノードの最小数は次のとおりです。 h+1 。
• ノードの数が最小の場合、ツリーの高さは最大になります。逆に、ノードの数が最大の場合、ツリーの高さは最小になります。

バイナリ ツリーに「n」個のノードがある場合。

最小の高さは次のように計算できます。

私たちが知っているように、

n = 2^h+1-1

n+1 = 2^h+1

両側からログを取ると、

ログ₂(n+1) = log2(2)^h+1)

ログ₂(n+1) = h+1

h = ログ₂(n+1) - 1

最大高さは次のように計算できます。

私たちが知っているように、

宗教のリスト

n = h+1

h=n-1

二分木の種類

バイナリ ツリーには 4 つのタイプがあります。

完全/適切/厳密なバイナリ ツリー 完全なバイナリ ツリー 完璧な二分木 縮退した二分木 バランスの取れた二分木

1. 完全/適切/厳密なバイナリ ツリー

完全なバイナリ ツリーは、厳密なバイナリ ツリーとも呼ばれます。各ノードに 0 個または 2 個の子が含まれている必要がある場合、ツリーは完全なバイナリ ツリーと見なすことができます。完全なバイナリ ツリーは、各ノードにリーフ ノードを除く 2 つの子が含まれている必要があるツリーとして定義することもできます。

フルバイナリツリーの簡単な例を見てみましょう。

上のツリーでは、各ノードに 0 個または 2 個の子が含まれていることがわかります。したがって、これは完全なバイナリ ツリーです。

完全なバイナリ ツリーのプロパティ

• リーフ ノードの数は、内部ノードの数に 1 を加えたものに等しくなります。上の例では、内部ノードの数は 5 です。したがって、リーフ ノードの数は 6 になります。
• ノードの最大数はバイナリ ツリー内のノードの数と同じ、つまり 2 です。^h+1-1.
• 完全なバイナリ ツリー内のノードの最小数は 2*h-1 です。
• 完全なバイナリ ツリーの最小高さは次のとおりです。 ログ₂(n+1) - 1。
• 完全なバイナリ ツリーの最大高さは次のように計算できます。

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Javaのメインメソッド

完全なバイナリ ツリー

完全な二分木は、最後のレベルを除いてすべてのノードが完全に満たされた木です。最後のレベルでは、すべてのノードを可能な限り残す必要があります。完全なバイナリ ツリーでは、ノードは左から追加する必要があります。

ループバッシュ用

完全なバイナリ ツリーを作成してみましょう。

上記のツリーは、すべてのノードが完全に埋められ、最終レベルのすべてのノードが最初に左側に追加されるため、完全なバイナリ ツリーです。

完全な二分木のプロパティ

• 完全なバイナリ ツリーの最大ノード数は 2 です^h+1- 1.
• 完全なバイナリ ツリーの最小ノード数は 2 です^h。
• 完全なバイナリ ツリーの最小高さは次のとおりです。 ログ₂(n+1) - 1。
• 完全なバイナリ ツリーの最大高さは次のとおりです。

完璧な二分木

すべての内部ノードに 2 つの子があり、すべての葉ノードが同じレベルにある場合、ツリーは完全な二分木になります。

完璧な二分木の簡単な例を見てみましょう。

以下のツリーは、すべてのリーフ ノードが同じレベルにないため、完全なバイナリ ツリーではありません。

注: すべての完全なバイナリ ツリーは完全なバイナリ ツリーであると同時に完全なバイナリ ツリーでもありますが、その逆は当てはまりません。つまり、すべての完全なバイナリ ツリーと完全なバイナリ ツリーは完全なバイナリ ツリーです。

縮退したバイナリ ツリー

縮退バイナリ ツリーは、すべての内部ノードが 1 つの子だけを持つツリーです。

例を通して縮退バイナリ ツリーを理解しましょう。

すべてのノードには子が 1 つしかないため、上記のツリーは縮退したバイナリ ツリーです。すべてのノードが右の子のみを持つため、右に歪んだツリーとも呼ばれます。

すべてのノードに子が 1 つしかないため、上記のツリーも縮退二分木になります。すべてのノードが左の子のみを持つため、左に歪んだツリーとも呼ばれます。

バランスの取れた二分木

バランスの取れた二分木は、左右の木が最大 1 だけ異なる木です。たとえば、次のようになります。 AVL そして 赤黒の木 バランスの取れた二分木です。

Java数学クラス

例を通してバランスの取れた二分木を理解しましょう。

左のサブツリーと右のサブツリーの差がゼロであるため、上のツリーはバランスの取れた二分木です。

左のサブツリーと右のサブツリーの差が 1 より大きいため、上のツリーは平衡二分木ではありません。

バイナリツリーの実装

バイナリ ツリーはポインタを使用して実装されます。ツリー内の最初のノードはルート ポインタによって表されます。ツリー内の各ノードは、データ、左ポインタ、右ポインタの 3 つの部分で構成されます。バイナリ ツリーを作成するには、まずノードを作成する必要があります。以下に示すようにユーザー定義のノードを作成します。

 struct node { int data, struct node *left, *right; } 

上記の構造では、 データ 値です、 左ポインタ 左側のノードのアドレスが含まれており、 右ポインタ 右ノードのアドレスが含まれます。

C のバイナリ ツリー プログラム

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

上記のコードは、create() 関数を再帰的に呼び出し、再帰呼び出しごとに新しいノードを作成します。すべてのノードが作成されると、バイナリ ツリー構造が形成されます。ノードを訪問するプロセスは、ツリー トラバーサルとして知られています。ノードへのアクセスには 3 つのタイプのトラバーサルが使用されます。

• インオーダートラバーサル
• 事前注文トラバーサル
• 郵便注文のトラバース