C语言实现基于二叉树的排序算法 - 数据结构实验报告

实验题目：基于二叉树的排序算法实现

实验目的

通过实现基于二叉树的排序算法，加深对数据结构的理解，并提高算法实现能力。

实验内容

1. 实现二叉树的创建、插入、删除等基本操作。
2. 实现二叉树的中序遍历算法。
3. 实现基于二叉树的排序算法。

实验步骤

1. 利用结构体定义二叉树节点：

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

2. 实现节点的创建操作：

TreeNode* create_node(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

3. 实现节点的插入操作：

void insert_node(TreeNode **root, int data) {
    if (*root == NULL) {
        *root = create_node(data);
        return;
    }
    if (data < (*root)->data) {
        insert_node(&((*root)->left), data);
    } else {
        insert_node(&((*root)->right), data);
    }
}

4. 实现节点的删除操作：

TreeNode* delete_node(TreeNode *root, int data) {
    if (root == NULL) return root;
    if (data < root->data) {
        root->left = delete_node(root->left, data);
    } else if (data > root->data) {
        root->right = delete_node(root->right, data);
    } else {
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        TreeNode *temp = find_min(root->right);
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

5. 实现中序遍历算法：

void inorder_traversal(TreeNode *root) {
    if (root != NULL) {
        inorder_traversal(root->left);
        printf('%d ', root->data);
        inorder_traversal(root->right);
    }
}

6. 实现基于二叉树的排序算法：

void binary_sort(int arr[], int n) {
    TreeNode *root = NULL;
    for (int i = 0; i < n; i++) {
        insert_node(&root, arr[i]);
    }
    inorder_traversal(root);
}

实验结果

输入数据：{5, 2, 7, 1, 3, 6, 8, 4}

输出结果：1 2 3 4 5 6 7 8

实验总结

通过本次实验，我成功地实现了基于二叉树的排序算法，并加深了对数据结构的理解。在实现过程中，我遇到了一些问题，例如节点的删除操作需要考虑多种情况，需要仔细思考和调试。通过不断地尝试和学习，我最终成功地完成了实验。我相信，通过不断地实践和探索，我将能够更好地掌握数据结构的知识，并在以后的工作中发挥更大的作用。