用c++设计一个与二叉树基本操作相关的演示程序。 要求: (1)创建二叉树。按照用户需要的二叉树,构建二叉树。 (2)分别以先序、中序、后序三种遍历访问二叉树。 (3)输出二叉树的叶子结点。(3)计算叶子结点的个数。(5)显示二叉树 (5)可循环创建二叉树(4)输出二叉树的高度。
时间: 2023-12-10 22:09:43 浏览: 31
好的,我会根据您的要求为您回答。以下是一个简单的二叉树演示程序,使用了C++语言。
```cpp
#include <iostream>
using namespace std;
// 二叉树节点结构体
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
}
};
// 创建二叉树
void createBinaryTree(Node* &root) {
int data;
cout << "请输入节点的值(-1表示节点为空):" << endl;
cin >> data;
if (data == -1) {
root = NULL;
return;
}
root = new Node(data);
createBinaryTree(root->left);
createBinaryTree(root->right);
}
// 先序遍历
void preOrderTraversal(Node* root) {
if (root == NULL) {
return;
}
cout << root->data << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍历
void inOrderTraversal(Node* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
// 后序遍历
void postOrderTraversal(Node* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->data << " ";
}
// 计算叶子结点的个数
int countLeafNodes(Node* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
// 叶子结点
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
// 输出叶子结点
void printLeafNodes(Node* root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
// 叶子结点
cout << root->data << " ";
return;
}
printLeafNodes(root->left);
printLeafNodes(root->right);
}
// 计算二叉树的高度
int getHeight(Node* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return 1 + max(leftHeight, rightHeight);
}
// 显示二叉树(使用中序遍历)
void displayBinaryTree(Node* root, int space) {
if (root == NULL) {
return;
}
space += 5;
displayBinaryTree(root->right, space);
cout << endl;
for (int i = 5; i < space; i++) {
cout << " ";
}
cout << root->data << endl;
displayBinaryTree(root->left, space);
}
int main() {
Node* root = NULL;
createBinaryTree(root);
cout << "先序遍历:";
preOrderTraversal(root);
cout << endl;
cout << "中序遍历:";
inOrderTraversal(root);
cout << endl;
cout << "后序遍历:";
postOrderTraversal(root);
cout << endl;
cout << "叶子结点:";
printLeafNodes(root);
cout << endl;
cout << "叶子结点个数:" << countLeafNodes(root) << endl;
cout << "二叉树高度:" << getHeight(root) << endl;
cout << "二叉树显示:" << endl;
displayBinaryTree(root, 0);
return 0;
}
```
该程序可以执行以下操作:
- 创建二叉树
- 先序遍历
- 中序遍历
- 后序遍历
- 输出二叉树的叶子结点
- 计算二叉树的叶子结点个数
- 显示二叉树
- 计算二叉树的高度
您可以根据需要对程序进行修改和扩展。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)