#include <iostream>#include <stack>using namespace std;struct Node {  Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {}  int item;  Node* left;  Node* right; }; Node* construct() {  Node* node6 = new Node(16);  Node* node5 = new Node(12);  Node* node4 = new Node(8);  Node* node3 = new Node(4);  Node* node2 = new Node(14, node5, node6);  Node* node1 = new Node(6, node3, node4);  Node* node0 = new Node(10, node1, node2);  return node0; }//遞歸算法void inorder(Node *root){ if (root == NULL) return; inorder(root->left); cout << root->item << " "; inorder(root->right);}void preorder(Node *root){ if(root == NULL) return; cout << root->item << " "; preorder(root->left); preorder(root->right);}void postorder(Node *root){ if (root == NULL) return; postorder(root->left); postorder(root->right); cout << root->item << " ";}void postorder2(Node *root){ if (root == NULL) return; stack<Node *> nstack; Node *pre = NULL; nstack.push(root); Node *node = NULL; while (!nstack.empty()) { node = nstack.top(); if (pre != node->left && pre != node->right) {  if (node->right)  nstack.push(node->right);  if (node->left)  nstack.push(node->left); } if (node->left == NULL && node->right == NULL   || pre == node->left || pre == node->right) {  cout << node->item << " ";  nstack.pop(); } pre = node; }}void preorder2(Node *root){ if(root == NULL) return; stack<Node *> nstack; Node *node = root; while (node != NULL || !nstack.empty()) { while(node != NULL) {  cout << node->item << " ";  nstack.push(node);  node = node->left; } node = nstack.top(); nstack.pop(); node = node->right; }}void preorder3(Node *root){ if (root == NULL) return; stack<Node *> nstack; nstack.push(root); Node *node = NULL; while (!nstack.empty()) { node = nstack.top(); nstack.pop(); cout << node->item << " "; if (node->right)  nstack.push(node->right); if (node->left)  nstack.push(node->left); }}//迭代算法void inorder2(Node *root){ if(root == NULL) return; stack<Node *> nstack; nstack.push(root); Node *next = root->left; while (next != NULL || !nstack.empty()) { while (next != NULL) {  nstack.push(next);  next = next->left; } next = nstack.top(); nstack.pop(); cout << next->item << " "; next = next->right; }}int main(){ Node *root = construct(); cout << "---------中序遍歷遞歸---------" << endl; inorder(root); cout << endl; cout << "---------中序遍歷迭代---------" << endl; inorder2(root); cout << endl; cout << "---------先序遍歷遞歸---------" << endl; preorder(root); cout << endl; cout << "---------先序遍歷迭代1---------" << endl; preorder2(root); cout << endl; cout << "---------先序遍歷迭代2---------" << endl; preorder3(root); cout << endl; cout << "---------后序遍歷遞歸---------" << endl; postorder(root); cout << endl; cout << "---------后序遍歷迭代---------" << endl; postorder2(root);}

void preOrderIterator(Node *root){ if (root == NULL) return; stack<Node*> nstack; nstack.push(root); while (!nstack.empty()) { Node *top = nstack.top(); while (top != NULL) {  if (top->left)  nstack.push(top->left);  cout << top->data << " ";  top = top->left; } while (top == NULL && !nstack.empty()) {  top = nstack.top()->right;  nstack.pop(); } if (top != NULL)  nstack.push(top); }}