C语言二叉树实验报告：基本操作实现与代码示例

实验目的：

本实验旨在掌握二叉树的基本概念和基本操作，了解二叉树的存储结构、遍历方式、查找、插入和删除等操作。

实验内容：

了解二叉树的定义及其性质。

二叉树是一种特殊的树形结构，每个节点至多只有两个子节点。二叉树具有以下性质：

每个节点最多有两个子节点。
左子树和右子树是有顺序的，不能颠倒。
即使某节点只有一个子节点，也要区分是左子节点还是右子节点。

实现二叉树的存储结构。

二叉树的存储结构有两种，分别是顺序存储结构和链式存储结构。本实验采用链式存储结构。定义一个二叉树结构体，包含节点值和指向左右子节点的指针。

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

实现二叉树的遍历方式。

二叉树的遍历方式有三种，分别是前序遍历、中序遍历和后序遍历。本实验实现了中序遍历的递归和非递归两种方式。

递归实现：

void inorderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf('%d ', root->data);
    inorderTraversal(root->right);
}

非递归实现：

void inorderTraversal2(Node *root) {
    Stack *stack = createStack();
    Node *p = root;
    while (p != NULL || !isEmpty(stack)) {
        while (p != NULL) {
            push(stack, p);
            p = p->left;
        }
        if (!isEmpty(stack)) {
            p = pop(stack);
            printf('%d ', p->data);
            p = p->right;
        }
    }
}

实现二叉树的查找、插入和删除操作。

(1) 查找操作： 在二叉树中查找给定的值。

Node *search(Node *root, int value) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == value) {
        return root;
    } else if (root->data > value) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}

(2) 插入操作： 向二叉树中插入一个新节点。

Node *insert(Node *root, int value) {
    if (root == NULL) {
        root = (Node *)malloc(sizeof(Node));
        root->data = value;
        root->left = NULL;
        root->right = NULL;
    } else if (root->data > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

(3) 删除操作： 从二叉树中删除一个节点。

Node *delete(Node *root, int value) {
    Node *temp;
    if (root == NULL) {
        printf('Value not found in the tree.');
    } else if (root->data > value) {
        root->left = delete(root->left, value);
    } else if (root->data < value) {
        root->right = delete(root->right, value);
    } else {
        if (root->left && root->right) {
            temp = findMax(root->left);
            root->data = temp->data;
            root->left = delete(root->left, root->data);
        } else {
            temp = root;
            if (root->left == NULL) {
                root = root->right;
            } else if (root->right == NULL) {
                root = root->left;
            }
            free(temp);
        }
    }
    return root;
}

实验结果：

本实验使用C语言实现了二叉树的存储结构、遍历方式、查找、插入和删除等操作。通过本次实验，我进一步掌握了数据结构中关于二叉树的相关知识，并提高了编程能力和问题解决能力。