树的遍历非递归实现---ShenduCC

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <map> #include <vector> #include <set> #include <queue> #include <stack> #include <math.h> using namespace std; struct Node { int val; Node* left; Node* right; Node(int value) { this->val = value; this->left=NULL; this->right=NULL; } }; void preOrder(Node* root) { if(root==NULL) return; cout<<root->val; preOrder(root->left); preOrder(root->right); } void inOrder(Node* root) { if(root==NULL) return; inOrder(root->left); cout<<root->val; inOrder(root->right); } void postOrder(Node* root) { if(root==NULL) return; postOrder(root->left); postOrder(root->right); cout<<root->val; } void buildTree(Node* &tree) { tree = new Node(4); tree->left = new Node(3); tree->left->left = new Node(5); //tree->left->left->right = new Node(10); //tree->left->left->right->left = new Node(11); tree->left->right = new Node(6); tree->right = new Node(7); tree->right->left = new Node(8); tree->right->right = new Node(9); } int main() { Node* tree; buildTree(tree); preOrder(tree); cout<<endl; stack<Node*> s; s.push(tree); while(!s.empty()) { Node* temp = s.top(); s.pop(); cout<<temp->val; if(temp->right!=NULL) s.push(temp->right); if(temp->left!=NULL) s.push(temp->left); } cout<<endl; Node* tree2=tree; cout << tree->val; s.push(tree); while(!s.empty()) { Node *temp = s.top(); if (temp->left != NULL) { cout << temp->left->val; s.push(temp->left); temp->left=NULL; continue; } s.pop(); if (temp->right != NULL) { cout << temp->right->val; s.push(temp->right); temp->right=NULL; continue; } } cout<<endl; buildTree(tree); Node* temp = tree; while(!s.empty()||temp!=NULL) { if(temp!=NULL) { cout<<temp->val; s.push(temp); temp=temp->left; } else { temp = s.top(); s.pop(); temp = temp->right; } } cout<<endl; inOrder(tree); cout<<endl; s.push(tree); while(!s.empty()) { Node* temp = s.top(); if(temp->left!=NULL) { s.push(temp->left); temp->left=NULL; continue; } cout<<temp->val; s.pop(); if(temp->right!=NULL) { s.push(temp->right); temp->right=NULL; continue; } } cout<<endl; buildTree(tree); temp = tree; while(!s.empty()||temp!=NULL) { if(temp!=NULL) { s.push(temp); temp=temp->left; } else{ temp = s.top(); cout<<temp->val; s.pop(); temp = temp->right; } } cout<<endl; buildTree(tree); postOrder(tree); cout<<endl; s.push(tree); while(!s.empty()) { Node* temp = s.top(); if(temp->left!=NULL) { s.push(temp->left); temp->left=NULL; continue; } if(temp->right!=NULL) { s.push(temp->right); temp->right=NULL; continue; } s.pop(); cout<<temp->val; } cout<<endl; buildTree(tree); s.push(tree); vector<int> ans; while(!s.empty()) { Node* temp = s.top(); s.pop(); ans.push_back(temp->val); if(temp->left!=NULL) s.push(temp->left); if(temp->right!=NULL) s.push(temp->right); } for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]; return 0; } ---来自腾讯云社区的---ShenduCC