ツリーの左子右兄弟表現
左-子右-兄弟表現は、n-aryツリーの異なる表現であり、すべての子ノードへのポインターを維持する代わりに、ノードは2つのポインター、最初は最初の子へのポインター、もう1つはへのポインターを保持します。そのすぐ次の兄弟。この新しい変換により、ノードが持つ子の数を事前に知る必要がなくなるだけでなく、ポインターの数が最大2つに制限されるため、コーディングが非常に簡単になります。
各ノードで、同じ親の子を左から右にリンクまたは接続します。
親は最初の子とのみリンクする必要があります。
例
左子右兄弟ツリー表現
10 | 2 -> 3 -> 4 -> 5 | | 6 7 -> 8 -> 9
利点
- この表現は、ノードごとに必要なポインタの最大数を2つに制限することにより、メモリを節約します。
- コーディングは簡単です。
短所
- 検索/挿入/削除などの基本的な操作は、正確な位置を選択するために、検索/挿入/削除するノードのすべての兄弟をトラバースする必要があるため、時間がかかります（最悪の場合）。
-
データ構造における二分木探索
このセクションでは、バイナリ検索ツリーに存在するキーをトラバースするためのさまざまなトラバーサルアルゴリズムについて説明します。これらのトラバーサルは、インオーダートラバーサル、プレオーダートラバーサル、ポストオーダートラバーサル、およびレベルオーダートラバーサルです。 このようなツリーが1つあるとします- インオーダートラバーサルシーケンスは、-5 8 10 15 16 20 23のようになります。 プレオーダートラバーサルシーケンスは、-10 5 8 16 15 20 23のようになります。 ポストオーダートラバーサルシーケンスは次のようになります− 8 5 15 23 20
-
データ構造における二分木表現
ここでは、コンピュータのメモリでバイナリツリーを表現する方法を説明します。表現するには2つの異なる方法があります。これらは配列とリンクリストを使用しています。 このようなツリーが1つあるとします- 配列表現は、レベル順の方法を使用して要素をスキャンすることにより、ツリーデータを格納します。したがって、ノードをレベルごとに格納します。一部の要素が欠落している場合は、空白のままにします。上記のツリーの表現は以下のようになります- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 5