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;
}