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

樹

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

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

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

操作

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

圖

• 是一個集合的數(shù)據(jù)結(jié)構(gòu)，其中的元素是頂點，它們通過邊連接在一起
• 邊可以是帶權(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)建圖
• 添加邊
• 遍歷圖
• 查找最短路徑

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

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

 // 創(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é)點有兩個子節(jié)點，則找到前驅(qū)（左子樹中最右節(jié)點）或後繼（右子樹中最左節(jié)點）
        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語言數(shù)據(jù)結(jié)構(gòu)：樹和圖的數(shù)據(jù)表示與操作的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！