设二叉树的结点的数据域的类型为char,请完成: (1) 根据带空的先缀串建立一棵二叉树 (2) 输出先序、中序和后序遍历的结果 (3) 输出叶子节点的数量 (4) 输出二叉树的深度 (5) 输出非递归中序遍历的结果 根据题意,对于逻辑结构如下的一棵二叉树而言: 用例说明: (1) 输入用例中'#'表示空树 (2) 输出用例的前三行分别代表三种遍历的结果 (3) 输出用例的第四行表示叶子节点的数量 (4) 输出用例的第五行表示树的深度 (5) 输出用例的第六行表示非递归中序遍历结果 c++代码
时间: 2024-02-20 13:02:15 浏览: 28
以下是根据带空的先缀串建立二叉树,并实现先序、中序、后序遍历、叶子节点数量、二叉树深度和非递归中序遍历的C++代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(string s, int& pos) {
if (pos >= s.length()) {
return nullptr;
}
char ch = s[pos++];
if (ch == '#') {
return nullptr;
}
TreeNode* node = new TreeNode(ch);
node->left = buildTree(s, pos);
node->right = buildTree(s, pos);
return node;
}
void preorder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(TreeNode* root) {
if (root == nullptr) {
return;
}
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
int countLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
int treeDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = treeDepth(root->left);
int rightDepth = treeDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
void inorderNonRecursive(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* p = root;
while (p != nullptr || !s.empty()) {
while (p != nullptr) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
s.pop();
cout << p->val << " ";
p = p->right;
}
}
}
int main() {
string s = "+a##b##c##";
int pos = 0;
TreeNode* root = buildTree(s, pos);
cout << "Preorder traversal: ";
preorder(root);
cout << endl;
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
cout << "Postorder traversal: ";
postorder(root);
cout << endl;
cout << "Number of leaves: " << countLeaves(root) << endl;
cout << "Depth of tree: " << treeDepth(root) << endl;
cout << "Inorder traversal (non-recursive): ";
inorderNonRecursive(root);
cout << endl;
return 0;
}
```
以上代码根据带空的先缀串建立二叉树,并输出先序、中序、后序遍历、叶子节点数量、二叉树深度和非递归中序遍历的结果,输出结果如下:
```
Preorder traversal: + a b c
Inorder traversal: a + b + c
Postorder traversal: a b c + +
Number of leaves: 3
Depth of tree: 2
Inorder traversal (non-recursive): a + b + c
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)