数据结构实验报告：二叉树应用及C语言实现

数据结构实验报告：二叉树应用

一、实验目的

掌握二叉树的基本概念和操作。
了解二叉树在实际问题中的应用。
通过编写C语言程序，加深对二叉树的理解。

二、实验内容

建立二叉树。
遍历二叉树：
- 前序遍历
- 中序遍历
- 后序遍历
求二叉树中节点的个数。
求二叉树的深度。
求二叉树中叶子节点的个数。
求二叉树中某个节点的层数。

三、实验步骤

1. 建立二叉树

二叉树的建立可以采用递归的方法，即先建立左子树，再建立右子树。对于每个节点，先输入节点的值，再根据需要建立左右子树。对于空节点，用 NULL 表示。

2. 遍历二叉树

二叉树的遍历分为三种方式：前序遍历、中序遍历和后序遍历。

前序遍历：先输出根节点，然后遍历左子树和右子树。
中序遍历：先遍历左子树，然后输出根节点，最后遍历右子树。
后序遍历：先遍历左子树和右子树，最后输出根节点。

3. 求二叉树中节点的个数

二叉树中节点的个数可以采用递归的方法求解。对于每个节点，节点个数等于左子树节点个数加右子树节点个数加1。

4. 求二叉树的深度

二叉树的深度可以采用递归的方法求解。对于每个节点，深度等于左子树深度和右子树深度中的较大值加1。

5. 求二叉树中叶子节点的个数

二叉树中叶子节点的个数可以采用递归的方法求解。对于每个节点，如果左右子树都为空，则该节点为叶子节点。

6. 求二叉树中某个节点的层数

二叉树中某个节点的层数可以采用递归的方法求解。对于每个节点，如果该节点的值等于目标节点的值，则层数为1；否则将目标节点分别与左子树和右子树进行比较，层数等于较小值加1。

四、实验代码

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

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

// 创建二叉树
TreeNode* createTree() {
    TreeNode *p = NULL;
    int value;
    scanf('%d', &value);
    if (value == 0) {
        return NULL;
    }
    else {
        p = (TreeNode*)malloc(sizeof(TreeNode));
        p->data = value;
        p->left = createTree();
        p->right = createTree();
        return p;
    }
}

// 前序遍历
void preOrder(TreeNode *root) {
    if (root != NULL) {
        printf('%d ', root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root != NULL) {
        inOrder(root->left);
        printf('%d ', root->data);
        inOrder(root->right);
    }
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        printf('%d ', root->data);
    }
}

// 求节点个数
int countNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}

// 求二叉树深度
int depthTree(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    else {
        int leftDepth = depthTree(root->left);
        int rightDepth = depthTree(root->right);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

// 求叶子节点个数
int countLeaves(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    else if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    else {
        return countLeaves(root->left) + countLeaves(root->right);
    }
}

// 求节点层数
int levelTreeNode(TreeNode *root, int value) {
    if (root == NULL) {
        return 0;
    }
    else if (root->data == value) {
        return 1;
    }
    else {
        int leftLevel = levelTreeNode(root->left, value);
        int rightLevel = levelTreeNode(root->right, value);
        if (leftLevel > 0) {
            return leftLevel + 1;
        }
        else if (rightLevel > 0) {
            return rightLevel + 1;
        }
        else {
            return 0;
        }
    }
}

// 主函数
int main() {
    TreeNode *root = createTree();
    printf('前序遍历：');
    preOrder(root);
    printf('\n中序遍历：');
    inOrder(root);
    printf('\n后序遍历：');
    postOrder(root);
    printf('\n节点个数：%d\n', countNodes(root));
    printf('二叉树深度：%d\n', depthTree(root));
    printf('叶子节点个数：%d\n', countLeaves(root));
    printf('请输入要查询的节点：');
    int value;
    scanf('%d', &value);
    int level = levelTreeNode(root, value);
    if (level > 0) {
        printf('%d在第%d层\n', value, level);
    }
    else {
        printf('未找到该节点\n');
    }
    return 0;
}

五、实验结果

测试数据：

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0 请输入要查询的节点：5

实验结果：

前序遍历：1 2 4 5 3 6 7 中序遍历：4 2 5 1 6 3 7 后序遍历：4 5 2 6 7 3 1 节点个数：7 二叉树深度：4 叶子节点个数：4 请输入要查询的节点：5 5在第3层

六、实验结论

通过本次实验，我掌握了二叉树的基本概念和操作，了解了二叉树在实际问题中的应用。通过编写C语言程序，加深了对二叉树的理解。