二叉树非递归遍历实现完整代码
时间: 2024-03-01 16:47:58 浏览: 110
二叉树非递归遍历算法实现
二叉树的非递归遍历可以使用栈来实现。以下是二叉树的非递归前序、中序和后序遍历的完整代码实现:
```cpp
#include <iostream>
#include <stack>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
cout << node->val << " ";
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
}
// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (node != NULL || !st.empty()) {
while (node != NULL) {
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
cout << node->val << " ";
node = node->right;
}
}
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
TreeNode* lastVisited = NULL;
while (node != NULL || !st.empty()) {
while (node != NULL) {
st.push(node);
node = node->left;
}
TreeNode* topNode = st.top();
if (topNode->right == NULL || topNode->right == lastVisited) {
cout << topNode->val << " ";
st.pop();
lastVisited = topNode;
} else {
node = topNode->right;
}
}
}
int main() {
// 构造二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 非递归前序遍历
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
// 非递归中序遍历
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
// 非递归后序遍历
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
return 0;
}
```
阅读全文