C言語データ構造：ツリーとグラフのデータ表現と操作

C言語データ構造：ツリーとグラフのデータ表現と操作

木

• 階層データ構造です
• ノードで構成されている各ノードには、データ要素とその子ノードへのポインターが含まれています
• バイナリツリーは特別なタイプのツリーで、各ノードには最大2つの子ノードがあります。

データ表現

streenode {
    INTデータ;
    struct treenode *左;
    struct treenode *右;
};

動作します

• ツリーを作成します
• トラバーサルツリー（定義、注文、および次の注文）
• ツリーを検索します
• ノードを挿入します
• ノードを削除します

写真

• コレクションのデータ構造であり、要素は頂点であり、それらはエッジで接続されています。
• エッジは、権利の有無にかかわらずになります

データ表現

隣接するマトリックス：

 int adjmatrix [v] [v];

隣接するテーブル：

 struct adjlistnode {
    int dest;
    struct adjlistnode *next;
};

struct adjlist {
    struct adjlistnode *head;
};

structグラフ{
    int v;
    struct adjlist *array;
};

動作します

• グラフを作成します
• エッジを追加します
• トラバーサル図
• 最短パスを見つけます

実用的なケース：バイナリ検索ツリー

バイナリ検索ツリーは、データ要素がツリーに順番に保存されるバイナリツリーです。これにより、検索、挿入、削除操作が非常に効率的になります。

 //バイナリ検索ツリーstruct treeNode *createbst（int data）を作成する{
    struct treenode *root = malloc（sizeof（struct treenode））;
    root-> data = data;
    root-> left = root-> right = null;
    ルートを返します。
}

//要素を検索int searchbst（struct treenode *root、int data）{
    if（！root）{
        0を返します。
    } else if（root-> data == data）{
        返品1;
    } else if（data <root-> data）{
        return searchbst（root-> left、data）;
    } それ以外 {
        return searchbst（root-> right、data）;
    }
}

//バイナリ検索ツリーstruct treeNode *insertbst（struct treenode *root、int data）に挿入要素
    if（！root）{
        return createbst（data）;
    } else if（data <root-> data）{
        root-> left = insertbst（root-> left、data）;
    } else if（data> root-> data）{
        root-> right = insertbst（root-> right、data）;
    }
    ルートを返します。
}

//バイナリ検索ツリーstruct treeNode *deletebst（struct treenode *root、int data）の要素を削除します{
    if（！root）{
        nullを返します。
    } else if（data <root-> data）{
        root-> left = deletebst（root-> left、data）;
    } else if（data> root-> data）{
        root-> right = deletebst（root-> right、data）;
    } それ以外 {
        //ノードに2つの子ノードがある場合、前身（左サブツリーの右端ノード）または後継者（右サブツリーの左端ノード）を見つけます
        if（root-> left && root->右）{
            int後継者= root->右> data;
            root-> data =後継者;
            root-> right = deletebst（root-> right、後継者）;
        } else if（root-> left）{
            struct treenode *temp = root-> left;
            無料（root）;
            return temp;
        } else if（root-> right）{
            struct treenode *temp = root-> right;
            無料（root）;
            return temp;
        } それ以外 {
            無料（root）;
            nullを返します。
        }
    }
    ルートを返します。
}

以上がC言語データ構造：ツリーとグラフのデータ表現と操作の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。