实现二叉树的基本操作:建立、遍历、计算深度、结点数、叶子数等。 输入C,先序创建二叉树,#表示空节点; 输入H:计算二叉树的高度; 输入L:计算二叉树的叶子个数; 输入N:计算二叉树节点总个数; 输入1:先序遍历二叉树; 输入2:中序遍历二叉树; 输入3:后续遍历二叉树; 输入F:查找值=x的节点的个数; 输入P:以缩格文本形式输出所有节点。 用C++语言实现
时间: 2024-01-23 10:09:21 浏览: 40
好的,我知道了。以下是用C++实现二叉树的基本操作的代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 建立二叉树
void createTree(TreeNode* &root) {
char val;
cin >> val;
if (val == '#') {
root = NULL;
} else {
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << ' ';
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << ' ';
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << ' ';
}
// 计算深度
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
// 计算节点数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftNodes = countNodes(root->left);
int rightNodes = countNodes(root->right);
return leftNodes + rightNodes + 1;
}
// 计算叶子节点数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int leftLeaves = countLeaves(root->left);
int rightLeaves = countLeaves(root->right);
return leftLeaves + rightLeaves;
}
// 查找值=x的节点的个数
int countValue(TreeNode* root, char x) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->val == x) {
count++;
}
count += countValue(root->left, x);
count += countValue(root->right, x);
return count;
}
// 以缩格文本形式输出所有节点
void printTree(TreeNode* root, int depth) {
if (root == NULL) {
return;
}
printTree(root->right, depth + 1);
for (int i = 0; i < depth; i++) {
cout << " ";
}
cout << root->val << endl;
printTree(root->left, depth + 1);
}
int main() {
TreeNode* root = NULL;
char command;
while (cin >> command) {
if (command == 'C') {
createTree(root);
} else if (command == '1') {
preorderTraversal(root);
cout << endl;
} else if (command == '2') {
inorderTraversal(root);
cout << endl;
} else if (command == '3') {
postorderTraversal(root);
cout << endl;
} else if (command == 'H') {
cout << maxDepth(root) << endl;
} else if (command == 'L') {
cout << countLeaves(root) << endl;
} else if (command == 'N') {
cout << countNodes(root) << endl;
} else if (command == 'F') {
char x;
cin >> x;
cout << countValue(root, x) << endl;
} else if (command == 'P') {
printTree(root, 0);
}
}
return 0;
}
```
你可以先输入C,然后按照先序遍历的顺序输入二叉树的节点,其中#表示空节点。然后,你可以输入相应的命令来进行二叉树的操作。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)