写一篇关于数据结构二叉树应用的实验报告要求用C语言写出实验代码

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

一、实验目的

1.掌握二叉树的基本概念和操作。

2.了解二叉树在实际问题中的应用。

3.通过编写C语言程序，加深对二叉树的理解。

二、实验内容

1.建立二叉树。

2.遍历二叉树。

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

4.求二叉树的深度。

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

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

三、实验步骤

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语言程序，加深了对二叉树的理解