C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)：樹和圖的數(shù)據(jù)表示與操作

樹

• 是一個(gè)層次結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)
• 由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和指向其子節(jié)點(diǎn)的指針
• 二叉樹是一種特殊類型的樹，其中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)

數(shù)據(jù)表示

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

操作

• 創(chuàng)建樹
• 遍歷樹（先序、中序、后序）
• 搜索樹
• 插入節(jié)點(diǎn)
• 刪除節(jié)點(diǎn)

圖

• 是一個(gè)集合的數(shù)據(jù)結(jié)構(gòu)，其中的元素是頂點(diǎn)，它們通過邊連接在一起
• 邊可以是帶權(quán)或無權(quán)的

數(shù)據(jù)表示

鄰接矩陣：

int adjMatrix[V][V];

鄰接表：

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

struct AdjList {
    struct AdjListNode *head;
};

struct Graph {
    int V;
    struct AdjList *array;
};

操作

• 創(chuàng)建圖
• 添加邊
• 遍歷圖
• 查找最短路徑

實(shí)戰(zhàn)案例：二叉查找樹

二叉查找樹是一種二叉樹，其數(shù)據(jù)元素在樹中按順序存儲(chǔ)。這使得搜索、插入和刪除操作非常高效。

// 創(chuàng)建二叉查找樹
struct TreeNode *createBST(int data) {
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->data = data;
    root->left = root->right = NULL;
    return root;
}

// 在二叉查找樹中搜索元素
int searchBST(struct TreeNode *root, int data) {
    if (!root) {
        return 0;
    } else if (root->data == data) {
        return 1;
    } else if (data < root->data) {
        return searchBST(root->left, data);
    } else {
        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);
    }
    return root;
}

// 在二叉查找樹中刪除元素
struct TreeNode *deleteBST(struct TreeNode *root, int data) {
    if (!root) {
        return NULL;
    } else if (data < root->data) {
        root->left = deleteBST(root->left, data);
    } else if (data > root->data) {
        root->right = deleteBST(root->right, data);
    } else {
        // 如果節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則找到前驅(qū)（左子樹中最右節(jié)點(diǎn)）或后繼（右子樹中最左節(jié)點(diǎn)）
        if (root->left && root->right) {
            int successor = root->right->data;
            root->data = successor;
            root->right = deleteBST(root->right, successor);
        } else if (root->left) {
            struct TreeNode *temp = root->left;
            free(root);
            return temp;
        } else if (root->right) {
            struct TreeNode *temp = root->right;
            free(root);
            return temp;
        } else {
            free(root);
            return NULL;
        }
    }
    return root;
}

以上是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)：樹和圖的數(shù)據(jù)表示與操作的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！