C語言數據結構：樹和圖的數據表示與操作

C語言數據結構：樹和圖的數據表示與操作

樹

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

數據表示

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

操作

• 創建樹
• 遍歷樹（先序、中序、後序）
• 搜索樹
• 插入節點
• 刪除節點

圖

• 是一個集合的數據結構，其中的元素是頂點，它們通過邊連接在一起
• 邊可以是帶權或無權的

數據表示

鄰接矩陣：

 int adjMatrix[V][V];

鄰接表：

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

struct AdjList {
    struct AdjListNode *head;
};

struct Graph {
    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;
    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 {
        // 如果節點有兩個子節點，則找到前驅（左子樹中最右節點）或後繼（右子樹中最左節點）
        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語言數據結構：樹和圖的數據表示與操作的詳細內容。更多資訊請關注PHP中文網其他相關文章！