用C++写一个二叉树的先序遍历的非递归算法
时间: 2023-12-03 10:03:55 浏览: 27
以下是C++实现二叉树的先序遍历的非递归算法:
```cpp
#include <iostream>
#include <stack>
using namespace std;
// 二叉树结点的定义
struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(NULL), right(NULL) {}
};
// 非递归先序遍历二叉树
void preorderTraversal(Node* root) {
if (root == NULL) return;
stack<Node*> s;
s.push(root);
while (!s.empty()) {
Node* cur = s.top();
s.pop();
cout << cur->val << " ";
if (cur->right) s.push(cur->right);
if (cur->left) s.push(cur->left);
}
}
int main() {
// 构造二叉树
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// 非递归先序遍历二叉树
preorderTraversal(root);
return 0;
}
```
代码中,首先定义了一个二叉树结点的结构体,包含结点值和左右子树指针。然后定义了一个非递归先序遍历函数 `preorderTraversal`,利用栈实现先序遍历。首先将根结点压入栈中,然后弹出栈顶结点,输出其值,并将其右子树和左子树压入栈中。重复这个过程,直到栈为空。最后在 `main` 函数中构造二叉树,并调用 `preorderTraversal` 函数进行非递归先序遍历。