バイナリツリーのリンクされたストレージ構造とは何ですか?

バイナリ ツリーのリンク ストレージ構造とは、リンク リストを使用してバイナリ ツリーを表現すること、つまり、リンク リストを使用して要素間の論理関係を示すことを指します。バイナリ ツリーのリンク ストレージ構造には、通常、バイナリ リンク リストとトリプレット リンク リストの 2 つのストレージ形式があります。

• リンクされたリストの各ノードは 3 つのフィールドで構成されます。データ フィールドに加えて、2 つのポインター フィールドもあります。ノードの左の子と右の子のストレージ アドレス。

• リンクされたリストの各ノードは 4 つのフィールドで構成されます。データ フィールドに加えて、3 つのポインタ フィールドもあり、これらはノードの左の子と右の子を与えるために使用されます。ノード、および親ノードが配置されているストレージ アドレス。

#バイナリツリーのリンクストレージ構造（C言語による詳細説明）

図1 通常の二分木の概略図
図 1 に示すように、これは通常の二分木であり、リンク リストに格納されている場合は、ツリーのルート ノードから開始して格納するだけで済みます。リンクされたリストを使用して、各ノードとその左右の子を接続するだけです。したがって、図 1 に対応するチェーン ストレージ構造を図 2 に示します。 図 2 バイナリ ツリーの連鎖ストレージ構造の概略図

図 2 から、バイナリ ツリーの連鎖ストレージが使用される場合、ノード構造は 3 つの部分で構成されていることがわかります (図 3 を参照)。

##左の子ノードへのポインタ (Lchild);

• 右の子ノードへのポインタ ポインタ (Rchild);
• 図 3 バイナリ ツリーのノード構造
  ノード構造を示す C 言語コード:

typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 struct BiTNode *parent; }BiTNode,*BiTree;

ログイン後にコピー

#include  #include  #define TElemType int typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->data=3; (*T)->rchild->lchild=NULL; (*T)->rchild->rchild=NULL; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->lchild->data=4; (*T)->lchild->rchild=NULL; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL; } int main() { BiTree Tree; CreateBiTree(&Tree); printf("%d",Tree->lchild->lchild->data); return 0; }

4

## 図 4 カスタム バイナリ ツリーのリンクされたストレージ構造

このようなリンク リスト構造は、通常、トリプル リンク リストと呼ばれます。

図 4 に示す 3 方向リンク リストを使用すると、各ノードの親ノードを簡単に見つけることができます。したがって、実際の問題を解決する場合、適切なリンク リスト構造を使用してバイナリ ツリーを格納すると、半分の労力で 2 倍の結果を達成できます。

関連する推奨事項: 「C 言語ビデオ チュートリアル
」

以上がバイナリツリーのリンクされたストレージ構造とは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。