假设二叉树中每个节点只为单个字符,采用二叉链存储结构,存储设计一个算法,采用先序遍历方法输出二叉树BT中所有节点的层次.用c++
时间: 2024-03-25 20:42:11 浏览: 24
好的,下面是该算法的C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
vector<int> getLevels(TreeNode* root) {
vector<int> levels;
stack<pair<TreeNode*, int>> st;
st.push(make_pair(root, 0));
while (!st.empty()) {
TreeNode* node = st.top().first;
int level = st.top().second;
st.pop();
if (node) {
if (levels.size() == level) {
levels.push_back(0);
}
levels[level] += 1;
st.push(make_pair(node->right, level + 1));
st.push(make_pair(node->left, level + 1));
}
}
return levels;
}
int main() {
// 构造一棵二叉树
TreeNode* root = new TreeNode('A');
root->left = new TreeNode('B');
root->right = new TreeNode('C');
root->left->left = new TreeNode('D');
root->left->right = new TreeNode('E');
root->right->left = new TreeNode('F');
root->right->right = new TreeNode('G');
root->left->left->left = new TreeNode('H');
root->left->left->right = new TreeNode('I');
root->left->right->left = new TreeNode('J');
root->right->right->left = new TreeNode('K');
root->right->right->right = new TreeNode('L');
vector<int> levels = getLevels(root);
for (int i = 0; i < levels.size(); i++) {
cout << "第" << i + 1 << "层的节点数为:" << levels[i] << endl;
}
return 0;
}
```
这个算法的时间复杂度是O(n),其中n是二叉树中节点的数量。