二叉树的建立、遍历及其应用 设树结点的元素类型为char,实现以下二叉树的各种基本操作的程序: ① 建立不少于10个结点的二叉树T; ②用后序遍历方式输出树T的结点; ③用层次遍历方式输出树T的结点; ④输出树T的深度; ⑤输出树T的叶子结点和非叶子结点; ⑥主函数通过函数调用实现以上各项操作
时间: 2024-02-16 16:04:37 浏览: 19
好的,我会尽力回答你的问题。以下是二叉树的建立、遍历及其应用的程序:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 定义二叉树结点
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
// 建立二叉树
TreeNode* buildTree() {
// 创建结点
TreeNode* root = new TreeNode('A');
TreeNode* nodeB = new TreeNode('B');
TreeNode* nodeC = new TreeNode('C');
TreeNode* nodeD = new TreeNode('D');
TreeNode* nodeE = new TreeNode('E');
TreeNode* nodeF = new TreeNode('F');
TreeNode* nodeG = new TreeNode('G');
TreeNode* nodeH = new TreeNode('H');
TreeNode* nodeI = new TreeNode('I');
TreeNode* nodeJ = new TreeNode('J');
// 建立结点之间的关系
root->left = nodeB;
root->right = nodeC;
nodeB->left = nodeD;
nodeB->right = nodeE;
nodeC->left = nodeF;
nodeC->right = nodeG;
nodeD->left = nodeH;
nodeD->right = nodeI;
nodeH->right = nodeJ;
return root;
}
// 后序遍历输出树的结点
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
// 层次遍历输出树的结点
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
}
// 计算树的深度
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
// 输出树的叶子结点和非叶子结点
void countLeafNode(TreeNode* root, int& leaf, int& nonLeaf) {
if (root == nullptr) return;
if (root->left == nullptr && root->right == nullptr) {
leaf++;
} else {
nonLeaf++;
}
countLeafNode(root->left, leaf, nonLeaf);
countLeafNode(root->right, leaf, nonLeaf);
}
int main() {
// 建立二叉树
TreeNode* root = buildTree();
// 后序遍历输出树的结点
cout << "后序遍历输出树的结点:" << endl;
postorderTraversal(root);
cout << endl;
// 层次遍历输出树的结点
cout << "层次遍历输出树的结点:" << endl;
levelOrderTraversal(root);
cout << endl;
// 输出树的深度
cout << "树的深度为:" << maxDepth(root) << endl;
// 输出树的叶子结点和非叶子结点
int leaf = 0;
int nonLeaf = 0;
countLeafNode(root, leaf, nonLeaf);
cout << "树的叶子结点个数为:" << leaf << endl;
cout << "树的非叶子结点个数为:" << nonLeaf << endl;
return 0;
}
```
这个程序中,我们首先定义了二叉树结点的结构体 `TreeNode`,包括结点值 `val` 和左右子树指针 `left` 和 `right`。然后我们通过 `buildTree` 函数建立了一个不少于10个结点的二叉树。接着我们实现了四个基本操作:
1. `postorderTraversal` 函数用于后序遍历输出树的结点;
2. `levelOrderTraversal` 函数用于层次遍历输出树的结点;
3. `maxDepth` 函数用于计算树的深度;
4. `countLeafNode` 函数用于输出树的叶子结点和非叶子结点。
最后,在 `main` 函数中,我们调用了以上四个函数,并输出了它们的结果。