使用二叉链表创建一棵二叉树,并完成如下操作: (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()` 函数中,我们使用递归的方式销毁二叉树。