1

BSTのコードをいくつか見てきましたが、各ノードが構造体であることがわかります。これは必要ですか？

4

5 に答える 5

7 
int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

…</p>

これ以上先に進むつもりはありません。

一般的に、structs/ classesはあらゆる種類のリンクされたデータ構造に使用されます。また、一般的に、型システムの機能はすべて無効化または無視される可能性がありint、非常に苦痛な方法で1つの配列のすべて（ヒープ割り当てなど）を実行できます。

于 2010-02-08T05:33:46.253 に答える
4

いいえ、クラスの可能性があります。値を格納し、子を指す必要があるため、プリミティブにすることはできません。

さて、BSTを配列として表すこともできます。ここで、位置にあるノードの左と右の子は、それぞれi位置2 * i + 1と2 * i + 2にあります。ただし、サイズ変更について心配する必要があり、nullを表すために特別な値が必要になり、削除操作がかなり複雑になります。このアプローチは、学術的な演習以外のものとしてはお勧めしません。

于 2010-02-08T05:17:47.457 に答える
4

必須ではありません。
ただし、ノードに含まれるデータと2つのリンクが一緒になって論理エンティティを形成するため、通常、それらは構造体にまとめられます。これにより、ノードを引数として取る関数やノードを返す関数のコーディングが容易になります。

于 2010-02-08T05:24:21.147 に答える
1

いいえ、厳密には言えません。FORTRANの時代には、人々は並列配列または2次元配列を使用していました。

Dahl、Dijkstra、Hoareによる「StructuredProgramming」のTony Hoareのセクションでは、データの構造化とレコードの種類について説明しました。

于 2010-02-08T05:40:43.070 に答える
0

ペイロードがセンチメンタル値を許可する場合は、並列配列よりも簡単に実行できます。暗黙的なツリーを使用できます（つまり、リンクをまったく気にしないでください）。

payload_type a[tree_size];

リンク構造をコーディングする配列内の位置を含む、ペイロード値のみを含む長いフラット配列：

  • a[0]ルートです
  • a[1]ルート->左です
  • a[2]ルート->右です
  • a[3]ルート->左->左です
  • a[4]ルート->左->右です
  • ..。

位置iのノードの場合、左の場合は2 * i + 1に、右の場合は2 * i+2に移動します。

あなたはそれをすべてのセンチメンタル値に初期化し、物事を追加し始めます...

于 2010-02-10T20:06:04.867 に答える