用c++完成以下操作1.以二叉链表表示二叉树,建立一棵二叉树。2.输出二叉树的中序遍历结果。3.输出二叉树的前序遍历结果。4.输出二叉树的后序遍历结果。5.计算二叉树的深度。6.统计二叉树的结点个数 。7.统计二叉树的叶结点个数。8.统计二叉树的度为1的结点个数。9.输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-06-16 12:02:25 浏览: 86
以下是使用C++实现以上操作的代码:
```cpp
#include<iostream>
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class BinaryTree
{
public:
TreeNode* root;
BinaryTree(): root(nullptr){}
~BinaryTree(){}
void createTree(TreeNode* &node); // 建立二叉树
void inorderTraversal(TreeNode* node); // 中序遍历
void preorderTraversal(TreeNode* node); // 前序遍历
void postorderTraversal(TreeNode* node); // 后序遍历
int getDepth(TreeNode* node); // 计算深度
int getNodeNum(TreeNode* node); // 统计结点个数
int getLeafNum(TreeNode* node); // 统计叶结点个数
int getDegreeOneNum(TreeNode* node); // 统计度为1的结点个数
void printPath(TreeNode* node); // 输出从每个叶子结点到根结点的路径
};
void BinaryTree::createTree(TreeNode* &node)
{
int val;
cin >> val;
if(val == -1) // 如果输入-1,则表示该结点为nullptr
{
node = nullptr;
}
else
{
node = new TreeNode(val);
createTree(node->left);
createTree(node->right);
}
}
void BinaryTree::inorderTraversal(TreeNode* node)
{
if(node)
{
inorderTraversal(node->left);
cout << node->val << " ";
inorderTraversal(node->right);
}
}
void BinaryTree::preorderTraversal(TreeNode* node)
{
if(node)
{
cout << node->val << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
void BinaryTree::postorderTraversal(TreeNode* node)
{
if(node)
{
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->val << " ";
}
}
int BinaryTree::getDepth(TreeNode* node)
{
if(!node)
{
return 0;
}
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
return max(leftDepth, rightDepth) + 1;
}
int BinaryTree::getNodeNum(TreeNode* node)
{
if(!node)
{
return 0;
}
return getNodeNum(node->left) + getNodeNum(node->right) + 1;
}
int BinaryTree::getLeafNum(TreeNode* node)
{
if(!node)
{
return 0;
}
if(!node->left && !node->right)
{
return 1;
}
return getLeafNum(node->left) + getLeafNum(node->right);
}
int BinaryTree::getDegreeOneNum(TreeNode* node)
{
if(!node)
{
return 0;
}
int degree = (!!node->left) + (!!node->right); // 统计度数
if(degree == 1)
{
return getDegreeOneNum(node->left) + getDegreeOneNum(node->right) + 1;
}
else
{
return getDegreeOneNum(node->left) + getDegreeOneNum(node->right);
}
}
void BinaryTree::printPath(TreeNode* node)
{
if(!node)
{
return;
}
static int path[100];
static int index = 0;
if(!node->left && !node->right) // 如果是叶子结点,则输出路径
{
for(int i = index; i>=0; i--)
{
cout << path[i] << " ";
}
cout << endl;
}
else // 否则,递归遍历左右子树
{
path[index++] = node->val;
printPath(node->left);
printPath(node->right);
index--;
}
}
int main()
{
BinaryTree tree;
cout << "请输入一棵二叉树(-1表示nullptr):" << endl;
tree.createTree(tree.root);
cout << "中序遍历结果为:" << endl;
tree.inorderTraversal(tree.root);
cout << endl;
cout << "前序遍历结果为:" << endl;
tree.preorderTraversal(tree.root);
cout << endl;
cout << "后序遍历结果为:" << endl;
tree.postorderTraversal(tree.root);
cout << endl;
cout << "二叉树的深度为:" << tree.getDepth(tree.root) << endl;
cout << "二叉树的结点个数为:" << tree.getNodeNum(tree.root) << endl;
cout << "二叉树的叶结点个数为:" << tree.getLeafNum(tree.root) << endl;
cout << "二叉树的度为1的结点个数为:" << tree.getDegreeOneNum(tree.root) << endl;
cout << "从每个叶子结点到根结点的路径为:" << endl;
tree.printPath(tree.root);
return 0;
}
```
该程序可以通过输入一组整数来构建一棵二叉树,并且输出该二叉树的中序遍历、前序遍历、后序遍历结果,计算二叉树的深度、结点个数、叶结点个数和度为1的结点个数,并输出从每个叶子结点到根结点的路径。
阅读全文