c - ダブルリンクリストとバイナリツリーのノード構造の違いは何ですか？

Question

インタビューで、二重リンクリストと二分木のノード構造の違いについて尋ねられました。

二重リンクリスト構造

typedef struct
{
int data;
struct node * next;
struct node * prev;
}node;

二分木構造

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

使用方法以外はノード構造に違いはありません。違いを教えていただけませんか？

score 11 · Accepted Answer

あなたはあなた自身の質問に答えたと思います。ポインタ（next/prevとleft/right）の名前の明らかな違いを除いて、違いは次のとおりです。

二重リンクリストも循環的である場合、以下も当てはまります。

1つのノードを持つ循環二重リンクリストでは、へのn.nextリンクとへnのn.prevリンクもありますn。これは二分木では不可能です：n.leftそしてn.right同じノードにリンクしないでください。
n.next1つのノードを持つバイナリツリーでは、ノードn.prevを指すことはできません（つまり、ツリーは単なるリーフノードです）が、1つのノードを持つ循環二重リンクリストでは、両方のリンクに常に値があります（同じノードに対して）。
二分木では、またはのいずれかの値を持つことはオプションn.leftですn.right。二分木のバランスが取れていない場合は、すべてのノードにの値がありますが、の値はない可能性がありn.rightますn.left。これは、すべてのポインターが値を持つ循環二重リンクリストには当てはまりません。

構造とコンテンツに関しては、ノードは同じですが、ポインターの使用方法とその値の違いが異なります。

score 4 · Accepted Answer

一般化できます。二重リンクリストとバイナリツリーはどちらも、各ノードが最大2つの出力エッジを持つことができる有向グラフの例です（構造体に存在するポインターフィールドの数であるため）。

各データ構造には追加の制限があります（たとえば、どちらの場合も、ルートノードからグラフ全体に到達できますが、すべてのノードからグラフ全体に到達できるのは二重リンクリストのみです）。これらの制限はさまざまなデータ構造を特徴づけますが、ノードを表すために使用される構造体には影響しません。

各ノードがその親へのポインタを追加で持つバイナリツリーが必要な場合があります。その場合、2つの構造体は異なります。

score 3 · Accepted Answer

あなたは絶対に正しいです: 同じペイロードタイプ (あなたの場合はint) を仮定すると、これら 2 つのノードタイプのバイナリレイアウトは同一です。2 つのノードタイプを異なるものにするのは、2 つのポインタの使用のみです。

読みやすさを気にしない場合は、ノードを使用できます

typedef struct node {
    int data;
    struct node *p1;
    struct node *p2;
} node;

二分木と二重連結リストの両方を表します。ただし、コードがすぐに他のプログラマーに認識されにくくなるため、お勧めできません。

3 に答える 3