用c++完成以下操作1.以二叉链表表示二叉树,建立一棵二叉树。2.输出二叉树的中序遍历结果。3.输出二叉树的前序遍历结果。4.输出二叉树的后序遍历结果。5.计算二叉树的深度。6.统计二叉树的结点个数 。7.统计二叉树的叶结点个数。8.统计二叉树的度为1的结点个数。9.输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-06-16 13:02:29 浏览: 90
c++实现二叉树的一些基本操作
4星 · 用户满意度95%
好的,下面是用C++实现以上操作的代码:
```cpp
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct Node {
char data;
Node* left;
Node* right;
Node(char c) : data(c), left(NULL), right(NULL) {}
};
// 建立二叉树
Node* createBinaryTree() {
char c;
cin >> c;
if (c == '#') {
return NULL;
}
Node* root = new Node(c);
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
// 中序遍历
void inorderTraversal(Node* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
// 前序遍历
void preorderTraversal(Node* root) {
if (root == NULL) {
return;
}
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(Node* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
// 计算二叉树的深度
int getDepth(Node* root) {
if (root == NULL) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
// 统计二叉树的结点个数
int getNodeNum(Node* root) {
if (root == NULL) {
return 0;
}
return getNodeNum(root->left) + getNodeNum(root->right) + 1;
}
// 统计二叉树的叶结点个数
int getLeafNum(Node* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return getLeafNum(root->left) + getLeafNum(root->right);
}
// 统计二叉树的度为1的结点个数
int getDegreeOneNum(Node* root) {
if (root == NULL) {
return 0;
}
int degreeOneNum = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
degreeOneNum = 1;
}
return degreeOneNum + getDegreeOneNum(root->left) + getDegreeOneNum(root->right);
}
// 输出从根结点到叶子结点的路径
void printPathFromRootToLeaf(Node* root, stack<char>& path) {
if (root == NULL) {
return;
}
path.push(root->data);
if (root->left == NULL && root->right == NULL) {
while (!path.empty()) {
cout << path.top() << " ";
path.pop();
}
cout << endl;
}
printPathFromRootToLeaf(root->left, path);
printPathFromRootToLeaf(root->right, path);
path.pop();
}
int main() {
// 建立二叉树
Node* root = createBinaryTree();
// 中序遍历
cout << "中序遍历结果:";
inorderTraversal(root);
cout << endl;
// 前序遍历
cout << "前序遍历结果:";
preorderTraversal(root);
cout << endl;
// 后序遍历
cout << "后序遍历结果:";
postorderTraversal(root);
cout << endl;
// 计算二叉树的深度
cout << "二叉树的深度为:" << getDepth(root) << endl;
// 统计二叉树的结点个数
cout << "二叉树的结点个数为:" << getNodeNum(root) << endl;
// 统计二叉树的叶结点个数
cout << "二叉树的叶结点个数为:" << getLeafNum(root) << endl;
// 统计二叉树的度为1的结点个数
cout << "二叉树的度为1的结点个数为:" << getDegreeOneNum(root) << endl;
// 输出从根结点到叶子结点的路径
stack<char> path;
cout << "从每个叶子结点到根结点的路径:" << endl;
printPathFromRootToLeaf(root, path);
return 0;
}
```
以上代码实现了用二叉链表表示二叉树,并且完成了建立二叉树、中序遍历、前序遍历、后序遍历、计算二叉树的深度、统计二叉树的结点个数、统计二叉树的叶结点个数、统计二叉树的度为1的结点个数和输出从每个叶子结点到根结点的路径等操作。
阅读全文