Logo

菜单

Administrator
Administrator
发布于 2024-09-06 / 20 阅读
0
0

第4节：树（Tree）

#c语言

接下来我们继续学习更加复杂和高级的数据结构：树（Tree）。树是一种非常重要的数据结构，广泛应用于文件系统、数据库索引、图像处理等领域。我们将从二叉树开始，逐步深入到更复杂的树结构，如二叉搜索树（BST）和平衡树。

第4节：树（Tree）

4.1 二叉树的基本概念

**树（Tree）**是一种层次结构的数据结构，具有分层关系。每个树节点可以有零个或多个子节点。

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

  • 根节点（Root）：树的最顶端节点。
  • 叶节点（Leaf）：没有子节点的节点。
  • 父节点和子节点：有子节点的节点称为父节点，子节点是从属节点。

4.2 二叉树的链式存储结构

在C语言中，二叉树通常使用链式结构实现，每个节点包含数据和两个指针，分别指向左子节点和右子节点。

二叉树节点的定义

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点
struct Node {
    int data; // 节点数据
    struct Node* left; // 左子节点
    struct Node* right; // 右子节点
};

函数：创建新节点

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

4.3 二叉树的遍历

遍历是访问树中所有节点的过程。常见的二叉树遍历方式有三种：

  1. 前序遍历（Preorder Traversal）：先访问根节点，再访问左子树，最后访问右子树。
  2. 中序遍历（Inorder Traversal）：先访问左子树，再访问根节点，最后访问右子树。
  3. 后序遍历（Postorder Traversal）：先访问左子树，再访问右子树，最后访问根节点。

前序遍历

// 前序遍历二叉树
void preorderTraversal(struct Node* root) {
    if (root == NULL) return;
    printf("%d -> ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

中序遍历

// 中序遍历二叉树
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d -> ", root->data);
    inorderTraversal(root->right);
}

后序遍历

// 后序遍历二叉树
void postorderTraversal(struct Node* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d -> ", root->data);
}

完整示例：二叉树遍历

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("NULL\n");

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("NULL\n");

    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("NULL\n");

    return 0;
}

4.4 二叉搜索树（BST）

**二叉搜索树（Binary Search Tree, BST）**是一种特殊的二叉树，它满足以下性质：

  • 对于每个节点，左子树的所有节点值都小于该节点的值，右子树的所有节点值都大于该节点的值。

插入节点

// 在二叉搜索树中插入节点
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) { // 空树，新建节点作为根节点
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data); // 插入左子树
    } else if (data > root->data) {
        root->right = insert(root->right, data); // 插入右子树
    }

    return root; // 返回更新后的树
}

查找节点

// 在二叉搜索树中查找节点
struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key) { // 找到节点或到达空树
        return root;
    }

    if (key < root->data) {
        return search(root->left, key); // 在左子树中查找
    } else {
        return search(root->right, key); // 在右子树中查找
    }
}

删除节点

// 在二叉搜索树中删除节点
struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) return root;

    if (key < root->data) {
        root->left = deleteNode(root->left, key); // 在左子树中删除
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key); // 在右子树中删除
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // 获取右子树中的最小值节点
        struct Node* temp = root->right;
        while (temp && temp->left != NULL) {
            temp = temp->left;
        }

        // 用最小值节点替换当前节点
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data); // 删除最小值节点
    }
    return root;
}

完整示例：二叉搜索树操作

int main() {
    struct Node* root = NULL;

    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("NULL\n");

    printf("Searching for 40: %s\n", search(root, 40) ? "Found" : "Not Found");

    root = deleteNode(root, 20);
    printf("After deleting 20, inorder traversal: ");
    inorderTraversal(root);
    printf("NULL\n");

    return 0;
}

4.5 平衡二叉树（AVL树）

AVL树是一种自平衡的二叉搜索树，确保在插入和删除节点后，树的高度差不会超过1。每个节点会维护一个高度值，插入或删除节点后，通过旋转操作来平衡树。AVL树的插入、删除和查找操作的时间复杂度是O(log n)。

练习题

  1. 最大深度：编写一个函数，计算二叉树的最大深度。
  2. 判断二叉搜索树：实现一个函数，检查给定的二叉树是否为二叉搜索树。
  3. 层序遍历：编写一个函数，按层次遍历二叉树（即广度优先搜索）。
  4. 平衡二叉树的实现：实现AVL树，完成插入、删除和旋转操作。
  5. 前序遍历、中序遍历、后序遍历的迭代实现：使用栈实现三种遍历方式的迭代版本。

完成这些练习后，你将对树结构有深入的理解。如果你已经熟练掌握了树的基础，可以继续学习高级树结构（如红黑树、B树等）或深入理解**图（Graph）**数据结构。

第5节：图（Graph）
第2，3节

评论