编写一个程序,实现功能具体如下: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的结点个数; 7.统计二叉树的叶结点个数;
时间: 2024-08-12 08:07:29 浏览: 99
在C++中,我们可以使用结构体来表示二叉树节点,并利用链表的方式存储二叉树的结构。这里是一个简单的示例代码,实现了上述要求的功能:
```cpp
#include <iostream>
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉链表类,包含遍历和计算功能
class BinaryTree {
private:
TreeNode* root;
public:
BinaryTree(TreeNode* root = nullptr) : root(root) {}
// 中序遍历
void inorderTraversal() {
inorderHelper(root);
std::cout << "Inorder traversal: ";
}
void inorderHelper(TreeNode* node) {
if (node != nullptr) {
inorderHelper(node->left);
std::cout << node->val << " ";
inorderHelper(node->right);
}
}
// 前序遍历
void preorderTraversal() {
preorderHelper(root);
std::cout << "Preorder traversal: ";
}
void preorderHelper(TreeNode* node) {
if (node != nullptr) {
std::cout << node->val << " ";
preorderHelper(node->left);
preorderHelper(node->right);
}
}
// 后序遍历
void postorderTraversal() {
postorderHelper(root);
std::cout << "Postorder traversal: ";
}
void postorderHelper(TreeNode* node) {
if (node != nullptr) {
postorderHelper(node->left);
postorderHelper(node->right);
std::cout << node->val << " ";
}
}
// 计算深度
int depth(TreeNode* node = root) {
if (node == nullptr) return 0;
int leftDepth = depth(node->left);
int rightDepth = depth(node->right);
return std::max(leftDepth, rightDepth) + 1;
}
// 统计节点个数
int nodeCount(TreeNode* node = root) {
if (node == nullptr) return 0;
return 1 + nodeCount(node->left) + nodeCount(node->right);
}
// 统计叶节点个数
int leafCount(TreeNode* node = root) {
if (node == nullptr) return 0;
if (node->left == nullptr && node->right == nullptr) return 1;
return leafCount(node->left) + leafCount(node->right);
}
};
int main() {
// 创建并初始化二叉树
TreeNode* tree = new TreeNode(1);
tree->left = new TreeNode(2);
tree->right = new TreeNode(3);
tree->left->left = new TreeNode(4);
tree->left->right = new TreeNode(5);
// 测试以上方法
BinaryTree bt(tree);
bt.inorderTraversal();
bt.preorderTraversal();
bt.postorderTraversal();
std::cout << "Tree depth: " << bt.depth() << std::endl;
std::cout << "Total nodes: " << bt.nodeCount() << std::endl;
std::cout << "Leaf nodes: " << bt.leafCount() << std::endl;
return 0;
}
```
阅读全文