c++先序遍历非递归算法
时间: 2023-12-03 14:01:09 浏览: 26
先序遍历是二叉树遍历的一种方法,其遍历顺序为根节点、左子树、右子树。非递归的先序遍历算法可以使用栈来实现。
具体算法如下:
1. 创建一个空栈和一个空的结果列表。
2. 将根节点压入栈中。
3. 当栈不为空时,执行以下操作:
4. 弹出栈顶元素,并将其值添加到结果列表中。
5. 如果弹出的节点存在右子树,将右子树的根节点压入栈中。
6. 如果弹出的节点存在左子树,将左子树的根节点压入栈中。
7. 返回结果列表。
非递归的先序遍历算法利用栈的特性,先将根节点压入栈中,然后在循环中不断取出栈顶元素,并将其值添加到结果列表中。同时,将该节点的右子树和左子树分别压入栈中。这样,在弹出栈顶节点的时候,下一次循环会先访问其左子树,从而实现了先序遍历的顺序。
使用非递归的先序遍历算法,可以遍历二叉树的每个节点,并按照先序的顺序输出节点的值。
相关问题
C++编写先序遍历的非递归算法
下面是C++编写的先序遍历非递归算法:
```c++
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
if (root != nullptr) {
s.push(root); // 将根节点入栈
}
while (!s.empty()) {
TreeNode* node = s.top();
s.pop(); // 弹出栈顶节点
res.push_back(node->val); // 将节点值加入到结果中
if (node->right != nullptr) {
s.push(node->right); // 右子树入栈
}
if (node->left != nullptr) {
s.push(node->left); // 左子树入栈
}
}
return res;
}
};
```
该算法利用了栈来模拟递归过程,先将根节点入栈,然后每次弹出栈顶节点,并将其值加入到结果中,接着将右子树和左子树依次入栈。
先序遍历的非递归算法c++
先序遍历的非递归算法可以使用栈来实现。具体步骤如下:
1. 创建一个栈,并将根节点入栈。
2. 当栈不为空时,执行以下操作:
a. 弹出栈顶节点,并访问该节点。
b. 如果该节点有右子节点,则将右子节点入栈。
c. 如果该节点有左子节点,则将左子节点入栈。
3. 重复步骤2直到栈为空。
下面是 C++代码实现:
```c++
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
auto node = stk.top();
stk.pop();
cout << node->val << " ";
if (node->right) {
stk.push(node->right);
}
if (node->left) {
stk.push(node->left);
}
}
}
```
其中,`TreeNode` 表示二叉树的节点。你可以根据自己的需要进行更改。