编写一个程序,实现功能具体如下: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的结点个数; 7.统计二叉树的叶结点个数。用C++
时间: 2023-11-14 22:10:06 浏览: 44
以下是实现该功能的C++程序:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void buildTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = NULL;
}
else {
root = new TreeNode(val);
buildTree(root->left);
buildTree(root->right);
}
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
int depth(TreeNode* root) {
if (root == NULL) return 0;
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return max(leftDepth, rightDepth) + 1;
}
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
int countLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
TreeNode* root;
buildTree(root);
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
cout << "Depth: " << depth(root) << endl;
cout << "Number of nodes: " << countNodes(root) << endl;
cout << "Number of leaves: " << countLeaves(root) << endl;
return 0;
}
```
该程序使用了二叉链表来表示二叉树,并实现了以下功能:
1. 通过 `buildTree()` 函数建立一棵二叉树;
2. 通过 `inorderTraversal()` 函数输出二叉树的中序遍历结果;
3. 通过 `preorderTraversal()` 函数输出二叉树的前序遍历结果;
4. 通过 `postorderTraversal()` 函数输出二叉树的后序遍历结果;
5. 通过 `depth()` 函数计算二叉树的深度;
6. 通过 `countNodes()` 函数统计二叉树的结点个数;
7. 通过 `countLeaves()` 函数统计二叉树的叶结点个数。
其中, `buildTree()` 函数使用了递归的方法建立二叉树,读入一个整数,如果该整数为 -1,则表示该节点为空,否则创建一个新节点,并递归调用 `buildTree()` 函数建立左右子树。其他函数都是经典的二叉树遍历和计算算法,具体实现可以参考注释。