C语言实现二叉树基本操作实验报告

实验目的

掌握二叉树的基本操作及其应用。

实验内容

设计一个二叉树，并完成以下操作：

创建二叉树；
遍历二叉树（前序、中序、后序遍历）；
求二叉树的深度；
判断二叉树是否为空；
销毁二叉树。

实验步骤

定义二叉树结构体

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

创建二叉树

创建二叉树的方法有很多种，这里介绍一种递归创建的方法。从根节点开始，先输入根节点的值，再输入左子树和右子树，如果子树为空，则输入0。

node* create_tree() {
    node* root = NULL;
    int value;
    scanf('%d', &value);
    if (value != 0) {
        root = (node*)malloc(sizeof(node));
        root->data = value;
        root->left = create_tree();
        root->right = create_tree();
    }
    return root;
}

遍历二叉树

遍历二叉树的方法有前序遍历、中序遍历、后序遍历三种。这里介绍递归实现的方法。

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

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

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

求二叉树的深度

二叉树的深度等于左子树深度和右子树深度的较大值加1。

int depth(node* root) {
    if (root == NULL) {
        return 0;
    } else {
        int left_depth = depth(root->left);
        int right_depth = depth(root->right);
        return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
    }
}

判断二叉树是否为空

如果二叉树的根节点为空，则二叉树为空。

bool is_empty(node* root) {
    return root == NULL;
}

销毁二叉树

递归地销毁左子树和右子树，最后销毁根节点。

void destroy_tree(node* root) {
    if (root != NULL) {
        destroy_tree(root->left);
        destroy_tree(root->right);
        free(root);
    }
}

实验结果

使用以上代码可以成功创建二叉树，遍历二叉树并输出遍历结果，求二叉树深度，判断二叉树是否为空，销毁二叉树等操作。