用c++设计一个与二叉树基本操作相关的演示程序。 要求: (1)创建二叉树。按照用户需要的二叉树,构建二叉树。 (2)分别以先序、中序、后序三种遍历访问二叉树。 (3)输出二叉树的叶子结点。(3)计算叶子结点的个数。(5)显示已有二叉树 (4)输出二叉树的高度。
时间: 2024-01-23 09:06:23 浏览: 27
c++实现二叉树的一些基本操作
4星 · 用户满意度95%
以下是一个简单的二叉树演示程序的C++代码:
```c++
#include <iostream>
using namespace std;
// 二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createTree();
root->right = createTree();
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
// 输出叶子结点
void leafNode(TreeNode* root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
cout << root->val << " ";
}
leafNode(root->left);
leafNode(root->right);
}
// 计算叶子结点数目
int leafNodeNum(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return leafNodeNum(root->left) + leafNodeNum(root->right);
}
// 计算二叉树的高度
int treeHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
// 显示已有二叉树
void displayTree(TreeNode* root, int space) {
if (root == NULL) {
return;
}
space += 5;
displayTree(root->right, space);
cout << endl;
for (int i = 5; i < space; i++) {
cout << " ";
}
cout << root->val << endl;
displayTree(root->left, space);
}
int main() {
cout << "请输入二叉树的结点,-1表示该结点为空:" << endl;
TreeNode* root = createTree();
cout << "先序遍历结果为:";
preOrder(root);
cout << endl;
cout << "中序遍历结果为:";
inOrder(root);
cout << endl;
cout << "后序遍历结果为:";
postOrder(root);
cout << endl;
cout << "叶子结点为:";
leafNode(root);
cout << endl;
cout << "叶子结点数目为:" << leafNodeNum(root) << endl;
cout << "二叉树高度为:" << treeHeight(root) << endl;
cout << "已有二叉树:" << endl;
displayTree(root, 0);
return 0;
}
```
注意:上述代码没有进行输入校验,如输入数据不合法可能会导致程序崩溃。在实际开发中,应该对输入进行严格的校验。
阅读全文