stack<TreeNode*> s; TreeNode* p=root;
时间: 2023-11-17 08:05:00 浏览: 46
这是一段 C++ 代码,首先创建了一个栈(stack)对象 s,然后将二叉树的根节点指针 root 赋值给指针变量 p。
这段代码可能用于二叉树的遍历,具体而言,可能是深度优先遍历(DFS)中的前序遍历(先遍历当前节点,再遍历左子树和右子树)实现的一部分。在遍历过程中,我们可以使用栈来保存待遍历的节点。对于当前节点 p,先将其值输出(或者进行其他操作),然后将其右子树(如果存在)入栈,再将其左子树(如果存在)入栈。由于栈是后进先出的数据结构,因此每次从栈中取出的节点都会是下一个需要遍历的节点。这样,我们就可以完成整个树的遍历。
相关问题
vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* p = root;
这段代码是用来实现二叉树的前序遍历的。
首先,定义了一个 vector<int> 类型的变量 res,用来存储遍历结果。
接着,定义了一个 stack<TreeNode*> 类型的变量 s,用来存储待遍历的节点。将二叉树的根节点指针 root 赋值给指针变量 p。
接下来,进入循环,判断条件为:p 不为空,或者栈不为空。这个条件的意义是,只要二叉树还没有遍历完,就需要继续遍历。
在循环中,首先判断当前节点 p 是否为空。如果不为空,就将其值加入到 res 中,并将其入栈。然后将指针 p 移动到其左子树。
如果当前节点 p 为空,说明已经遍历完了当前子树。此时需要从栈中取出一个节点,将指针 p 指向其右子树。由于前序遍历的顺序是“根-左-右”,因此要先遍历右子树,再遍历左子树。
最后,当循环结束时,返回遍历结果 res 即可。
代码改进,不使用cout<<endl结构#include <iostream> #include <queue> #include <stack> #include <string> using namespace std; struct Student { string name; int number; int score; }; struct TreeNode { Student data; TreeNode* left; TreeNode* right; TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {} }; void postOrder(TreeNode* root) { if (!root) return; postOrder(root->left); postOrder(root->right); cout << root->data.name << " " << root->data.number << " " << root->data.score << endl; } void preOrder(TreeNode* root) { stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; s.push(node->right); s.push(node->left); } } } void levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; q.push(node->left); q.push(node->right); } } } int main() { Student students[] = { {"Lei Zhenzi", 101401, 82}, {"Jiang Ziya", 100032, 90}, {"Ne Zha", 101674, 70}, {"Shen Gongbao", 101982, 87}, {"Jiu Weihu", 107431, 75}, {"Tian Zun", 100001, 98}, {"Tai Yi", 101009, 81}, {"Yang Jian", 101321, 63}, {"Huang Feihu", 101567, 72}, {"Zhou Wang", 108160, 55}, {"Li Jing", 102456, 84}, {"Tu Xingsun", 102245, 65}, }; int n = sizeof(students) / sizeof(Student); TreeNode* root = new TreeNode(students[0]); queue<TreeNode*> q; q.push(root); for (int i = 1; i < n; i += 2) { TreeNode* parent = q.front(); q.pop(); parent->left = new TreeNode(students[i]); q.push(parent->left); if (i + 1 < n) { parent->right = new TreeNode(students[i + 1]); q.push(parent->right); } } cout << "Post-order traversal: " << endl; postOrder(root); cout << "Pre-order traversal: " << endl; preOrder(root); cout << "Level-order traversal: " << endl; levelOrder(root); return 0; }
可以使用'\n'代替endl,这样可以避免刷新缓存区的操作,提高输出效率。修改后的代码如下:
```
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;
struct Student {
string name;
int number;
int score;
};
struct TreeNode {
Student data;
TreeNode* left;
TreeNode* right;
TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {}
};
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->data.name << " " << root->data.number << " " << root->data.score << '\n';
}
void preOrder(TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node) {
cout << node->data.name << " " << node->data.number << " " << node->data.score << '\n';
s.push(node->right);
s.push(node->left);
}
}
}
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node) {
cout << node->data.name << " " << node->data.number << " " << node->data.score << '\n';
q.push(node->left);
q.push(node->right);
}
}
}
int main() {
Student students[] = {
{"Lei Zhenzi", 101401, 82},
{"Jiang Ziya", 100032, 90},
{"Ne Zha", 101674, 70},
{"Shen Gongbao", 101982, 87},
{"Jiu Weihu", 107431, 75},
{"Tian Zun", 100001, 98},
{"Tai Yi", 101009, 81},
{"Yang Jian", 101321, 63},
{"Huang Feihu", 101567, 72},
{"Zhou Wang", 108160, 55},
{"Li Jing", 102456, 84},
{"Tu Xingsun", 102245, 65},
};
int n = sizeof(students) / sizeof(Student);
TreeNode* root = new TreeNode(students[0]);
queue<TreeNode*> q;
q.push(root);
for (int i = 1; i < n; i += 2) {
TreeNode* parent = q.front();
q.pop();
parent->left = new TreeNode(students[i]);
q.push(parent->left);
if (i + 1 < n) {
parent->right = new TreeNode(students[i + 1]);
q.push(parent->right);
}
}
cout << "Post-order traversal: \n";
postOrder(root);
cout << "Pre-order traversal: \n";
preOrder(root);
cout << "Level-order traversal: \n";
levelOrder(root);
return 0;
}
```
相关推荐
![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)