使用二叉链表创建一棵二叉树,并完成如下操作: (1) 对这棵二叉树分别进行先序、中序、后序遍历; (2) 统计这棵二叉树的深度、叶子结点数、结点总数; (3) 销毁这棵二叉树。

时间: 2023-06-10 10:07:57 浏览: 44
首先,二叉链表是一种数据结构,可以用来表示二叉树。在二叉链表中,每个结点都有两个指针,分别指向其左子树和右子树。 下面是使用二叉链表创建一棵二叉树的代码: ```c++ #include <iostream> using namespace std; // 定义二叉树结点类型 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; // 创建二叉树 void createTree(TreeNode*& root) { int val; cin >> val; if (val == -1) { // 输入-1表示该结点为空 root = NULL; } else { root = new TreeNode(val); createTree(root->left); createTree(root->right); } } // 先序遍历 void preOrder(TreeNode* root) { if (root != NULL) { cout << root->val << " "; preOrder(root->left); preOrder(root->right); } } // 中序遍历 void inOrder(TreeNode* root) { if (root != NULL) { inOrder(root->left); cout << root->val << " "; inOrder(root->right); } } // 后序遍历 void postOrder(TreeNode* root) { if (root != NULL) { postOrder(root->left); postOrder(root->right); cout << root->val << " "; } } // 统计深度、叶子结点数和结点总数 void countNodes(TreeNode* root, int& depth, int& leaf, int& nodes) { if (root != NULL) { nodes++; if (root->left == NULL && root->right == NULL) { leaf++; } int ldepth = 0, rdepth = 0; countNodes(root->left, ldepth, leaf, nodes); countNodes(root->right, rdepth, leaf, nodes); depth = max(ldepth, rdepth) + 1; } } // 销毁二叉树 void destroyTree(TreeNode*& root) { if (root != NULL) { destroyTree(root->left); destroyTree(root->right); delete root; root = NULL; } } int main() { TreeNode* root; cout << "请输入二叉树的结点,-1表示空结点:" << endl; createTree(root); cout << "先序遍历结果:"; preOrder(root); cout << endl; cout << "中序遍历结果:"; inOrder(root); cout << endl; cout << "后序遍历结果:"; postOrder(root); cout << endl; int depth = 0, leaf = 0, nodes = 0; countNodes(root, depth, leaf, nodes); cout << "深度:" << depth << endl; cout << "叶子结点数:" << leaf << endl; cout << "结点总数:" << nodes << endl; destroyTree(root); return 0; } ``` 上述代码中,我们首先定义了二叉树结点的结构体类型 `TreeNode`,并定义了三个指向左子树、右子树和结点值的成员变量。在 `createTree()` 函数中,我们通过递归的方式创建二叉树,如果输入的值为-1,则表示该结点为空。 接下来,我们分别定义了三个遍历函数 `preOrder()`、`inOrder()` 和 `postOrder()`,分别实现二叉树的先序、中序和后序遍历。这三个函数的实现都采用了递归的方式,先访问左子树,然后访问右子树,最后访问根结点。 在 `countNodes()` 函数中,我们统计了二叉树的深度、叶子结点数和结点总数。在递归过程中,我们累计每个结点的深度,如果该结点没有左子树和右子树,则它是叶子结点,否则它不是叶子结点。最后,我们求出深度的最大值,加1即为二叉树的深度。 最后,在 `destroyTree()` 函数中,我们使用递归的方式销毁二叉树。

相关推荐

最新推荐

recommend-type

华为OD机试D卷 - 用连续自然数之和来表达整数 - 免费看解析和代码.html

私信博主免费获取真题解析以及代码
recommend-type

Screenshot_2024-05-10-20-21-01-857_com.chaoxing.mobile.jpg

Screenshot_2024-05-10-20-21-01-857_com.chaoxing.mobile.jpg
recommend-type

数字图像处理|Matlab-频域增强实验-彩色图像的频域滤波.zip

数字图像处理|Matlab-频域增强实验-彩色图像的频域滤波.zip
recommend-type

2024-2030中国定向转向膜市场现状研究分析与发展前景预测报告.docx

2024-2030中国定向转向膜市场现状研究分析与发展前景预测报告
recommend-type

开源工时填报管理系统安装包

开源工时填报管理系统安装包
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

spring添加xml配置文件

1. 创建一个新的Spring配置文件,例如"applicationContext.xml"。 2. 在文件头部添加XML命名空间和schema定义,如下所示: ``` <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.springframework.org/schema/beans
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。