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

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

#このチュートリアルの動作環境: Windows7 システム、C99 バージョン、Dell G3 コンピューター。

バイナリ ツリーのリンク ストレージ構造では、リンク リストを使用してバイナリ ツリーを表現します。つまり、リンク リストは要素間の論理関係を示すために使用されます。通常、2 つの格納形式があります:

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

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

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

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

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

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

ノードに格納されているデータ (data);

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

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

図 2 のチェーン ストレージ構造に対応する C 言語コード:

#include <stdio.h>
#include <stdlib.h>
#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

実際には、バイナリ ツリーのチェーン ストレージ構造は、図 2 に示されているものよりはるかに複雑です。たとえば、実際のシナリオでは、「ノードの親ノードを見つける」という操作が実行される場合があります。この場合、図に示すように、各ノードの親ノードを指すようにポインタ フィールドをノード構造に追加できます。図 4 ：

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

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

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

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

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