C语言实现二叉树应用实验报告

实验目的

本实验旨在熟悉二叉树的基本概念和操作，掌握二叉树的遍历方式，以及了解二叉树在实际应用中的一些常见场景。

实验内容

本实验内容包括以下几个部分：

二叉树的创建
二叉树的遍历
二叉树的一些应用实例

实验原理

二叉树的创建二叉树是一种特殊的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点，因此又称为左右子树。在二叉树中，每个节点都有一个唯一的父节点，除了根节点没有父节点。二叉树的创建可以通过递归和非递归方式实现。
二叉树的遍历二叉树的遍历方式有三种，分别为前序遍历、中序遍历和后序遍历。前序遍历是先访问根节点，然后按照先左后右的顺序遍历子树；中序遍历是按照先左后根再右的顺序遍历子树；后序遍历是按照先左后右再根的顺序遍历子树。
二叉树的一些应用实例二叉树在实际应用中有很多场景，比如文件系统的目录结构、编译器中的语法树、哈夫曼编码中的编码树等。

实验步骤

二叉树的创建本实验使用递归方式创建二叉树，具体步骤如下：（1）定义二叉树节点结构体；（2）实现递归方式创建二叉树的函数'createBinaryTree()'；（3）在主函数中调用'createBinaryTree()'函数创建二叉树。

代码实现如下：

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

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

struct TreeNode* createBinaryTree() {
    int data;
    struct TreeNode *node;
    printf("请输入节点的值（-1表示空节点）：");
    scanf("%d", &data);
    if (data == -1) {
        node = NULL;
    } else {
        node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->data = data;
        printf("请输入%d的左子节点：", data);
        node->left = createBinaryTree();
        printf("请输入%d的右子节点：", data);
        node->right = createBinaryTree();
    }
    return node;
}

int main() {
    struct TreeNode *root;
    root = createBinaryTree();
    printf("二叉树创建成功！\n");
    return 0;
}

二叉树的遍历本实验实现前序遍历、中序遍历和后序遍历三种遍历方式，具体步骤如下：（1）实现前序遍历函数'preOrderTraversal()'；（2）实现中序遍历函数'inOrderTraversal()'；（3）实现后序遍历函数'postOrderTraversal()'；（4）在主函数中调用三个遍历函数。

代码实现如下：

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

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

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

int main() {
    struct TreeNode *root;
    root = createBinaryTree();
    printf("前序遍历结果：");
    preOrderTraversal(root);
    printf("\n中序遍历结果：");
    inOrderTraversal(root);
    printf("\n后序遍历结果：");
    postOrderTraversal(root);
    return 0;
}

二叉树的一些应用实例本实验实现二叉树在文件系统的目录结构中的应用，具体步骤如下：（1）定义文件目录结构体；（2）实现递归方式创建文件目录树的函数'createFileTree()'；（3）在主函数中调用'createFileTree()'函数创建文件目录树；（4）实现前序遍历函数'preOrderTraversal()'；（5）在主函数中调用'preOrderTraversal()'函数遍历文件目录树。

代码实现如下：

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

struct FileInfo {
    char name[100];
    int type; // 0表示文件夹，1表示文件
    struct FileInfo *subFiles;
    struct FileInfo *next;
};

struct FileInfo* createFileTree() {
    struct FileInfo *node, *p, *q;
    char name[100];
    int type, flag;
    printf("请输入文件夹的名字：");
    scanf("%s", name);
    node = (struct FileInfo*)malloc(sizeof(struct FileInfo));
    strcpy(node->name, name);
    node->type = 0;
    node->subFiles = NULL;
    node->next = NULL;
    printf("该文件夹下是否有子文件（0表示没有，1表示有）：");
    scanf("%d", &flag);
    if (flag == 1) {
        printf("请输入子文件的个数：");
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            printf("请输入第%d个子文件的名字：", i + 1);
            scanf("%s", name);
            printf("该文件是文件还是文件夹（0表示文件夹，1表示文件）：");
            scanf("%d", &type);
            p = (struct FileInfo*)malloc(sizeof(struct FileInfo));
            strcpy(p->name, name);
            p->type = type;
            p->subFiles = NULL;
            p->next = NULL;
            if (node->subFiles == NULL) {
                node->subFiles = p;
            } else {
                q->next = p;
            }
            q = p;
            if (type == 0) {
                p->subFiles = createFileTree();
            }
        }
    }
    return node;
}

void preOrderTraversal(struct FileInfo *root, int level) {
    for (int i = 0; i < level; i++) {
        printf("    ");
    }
    printf("|-- %s\n", root->name);
    struct FileInfo *p = root->subFiles;
    while (p != NULL) {
        preOrderTraversal(p, level + 1);
        p = p->next;
    }
}

int main() {
    struct FileInfo *root;
    root = createFileTree();
    printf("文件目录树创建成功！\n");
    preOrderTraversal(root, 0);
    return 0;
}

实验总结

本实验通过递归方式创建二叉树，实现了二叉树的前序遍历、中序遍历和后序遍历三种遍历方式，同时介绍了二叉树在文件系统的目录结构中的应用。通过本次实验，我进一步加深了对二叉树的理解和运用，掌握了一些二叉树的基本操作和应用场景，对于今后的学习和工作都非常有帮助。