TreeNode* cur=st. top()是什么意思
时间: 2024-05-25 09:13:58 浏览: 11
这行代码是从栈中取出栈顶元素,并将其赋值给指针变量 `cur`。假设 `st` 是一个栈(stack),则 `top()` 是栈的一个成员函数,用于获取栈顶元素。注意,这里的 `TreeNode` 是一个自定义类型,可能是树结构中的一个节点类型。因此,`cur` 变量的类型应该是 `TreeNode*`,即指向 `TreeNode` 类型对象的指针。
相关问题
要求设计一个c++非递归代码,实现二叉树的后序遍历。 参考函数: struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(NULL), right(NULL) {} }; 输入说明 : 第一行:表示无孩子或指针为空的特殊分隔符 第二行:二叉树的先序序列(结点元素之间以空格分隔) 输出说明 : 第一行:后序遍历的结果 输入范例 : A B # C D # # E # # F # G # H # # 输出范例 : D,E,C,B,H,G,F,A
好的,根据你的要求,我已经设计好了一个c++非递归代码,实现二叉树的后序遍历。代码如下:
```c++
#include<iostream>
#include<stack>
#include<string>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
void postorder(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* last = NULL;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
}
else {
TreeNode* top = st.top();
if (top->right != NULL && last != top->right) {
cur = top->right;
}
else {
cout << top->val << " ";
last = top;
st.pop();
}
}
}
}
int main() {
string s;
getline(cin, s);
if (s == "#") {
cout << endl;
return 0;
}
TreeNode* root = new TreeNode(s[0]);
stack<TreeNode*> st;
st.push(root);
int i = 2;
while (i < s.size()) {
if (s[i] == '#') {
if (s[i - 1] == '#') {
st.pop();
}
else {
if (st.top()->left == NULL) {
st.top()->left = new TreeNode(s[i - 1]);
st.push(st.top()->left);
}
else {
st.top()->right = new TreeNode(s[i - 1]);
st.push(st.top()->right);
}
}
i += 2;
}
else {
if (s[i - 1] == '#') {
i += 2;
}
else {
if (st.top()->left == NULL) {
st.top()->left = new TreeNode(s[i - 1]);
st.push(st.top()->left);
}
else {
st.top()->right = new TreeNode(s[i - 1]);
st.push(st.top()->right);
}
i += 2;
}
}
}
postorder(root);
cout << endl;
return 0;
}
```
输入格式为先输入一个表示无孩子或指针为空的特殊分隔符,然后输入二叉树的先序序列(结点元素之间以空格分隔)。输出为后序遍历的结果。
c语言数据结构二叉树的非递归遍历代码
二叉树的非递归遍历通常使用栈来实现。以下是三种非递归遍历方式的代码实现:
1. 非递归中序遍历:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
if (cur != nullptr) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
}
```
2. 非递归先序遍历:
```
void preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
if (root != nullptr) {
st.push(root);
}
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
cout << cur->val << " ";
if (cur->right != nullptr) {
st.push(cur->right);
}
if (cur->left != nullptr) {
st.push(cur->left);
}
}
}
```
3. 非递归后序遍历:
```
void postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* prev = nullptr;
if (root != nullptr) {
st.push(root);
}
while (!st.empty()) {
TreeNode* cur = st.top();
if ((cur->left == nullptr && cur->right == nullptr) || (prev != nullptr && (prev == cur->left || prev == cur->right))) {
cout << cur->val << " ";
st.pop();
prev = cur;
} else {
if (cur->right != nullptr) {
st.push(cur->right);
}
if (cur->left != nullptr) {
st.push(cur->left);
}
}
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)