分别建立建立二叉树存储结构的的输入函数、输出先序、中序遍历、后序遍历序列的函数。并计算树的深度和结点数目。要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列,并计算树的深度和结点数目。用Dev-C++实现
时间: 2024-12-21 21:23:08 浏览: 3
在Dev-C++中,我们可以设计一系列函数来实现二叉树的存储、输入、遍历以及节点数和深度的计算。这里提供了一个基本的框架:
```cpp
#include<iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 输入二叉树函数
TreeNode* createTree() {
int val;
cout << "请输入二叉树的根节点值:";
cin >> val;
if (val == -1) return NULL; // 如果输入-1结束输入
TreeNode* root = new TreeNode(val);
root->left = createTree();
root->right = createTree();
return root;
}
// 先序遍历函数
void preOrder(TreeNode* node) {
if (node != NULL) {
cout << node->val << " ";
preOrder(node->left);
preOrder(node->right);
}
}
// 中序遍历函数
void inOrder(TreeNode* node) {
if (node != NULL) {
inOrder(node->left);
cout << node->val << " ";
inOrder(node->right);
}
}
// 后序遍历函数
void postOrder(TreeNode* node) {
if (node != NULL) {
postOrder(node->left);
postOrder(node->right);
cout << node->val << " ";
}
}
// 计算树深和节点数的辅助函数
int calculateDepth(TreeNode* node, int& depth) {
if (node == NULL) return 0;
depth++;
return max(calculateDepth(node->left, depth), calculateDepth(node->right, depth));
}
// 计算树的深度和节点数
void treeInfo(TreeNode* root) {
int depth = 0;
int count = 0;
if (root != NULL) {
depth = calculateDepth(root, depth);
cout << "树的深度为:" << depth << endl;
count = dfsCount(root); // 使用递归计算节点总数
cout << "树的节点总数为:" << count << endl;
} else {
cout << "树为空" << endl;
}
}
// 递归计算节点总数
int dfsCount(TreeNode* node) {
if (node == NULL) return 0;
return 1 + dfsCount(node->left) + dfsCount(node->right);
}
int main() {
TreeNode* root = createTree();
if (root != NULL) {
cout << "先序遍历结果:";
preOrder(root);
cout << endl;
cout << "中序遍历结果:";
inOrder(root);
cout << endl;
cout << "后序遍历结果:";
postOrder(root);
cout << endl;
treeInfo(root);
}
return 0;
}
```
这个程序实现了二叉树的基本操作,包括创建树、三种遍历方式以及计算树的深度和节点数。注意,在实际运行时,用户需要逐个输入每个节点的值,直到输入-1表示输入结束。
阅读全文