本文实例讲述了C语言实现二叉树遍历的迭代算法，是数据结构算法中非常经典的一类算法。分享给大家供大家参考。

具体实现方法如下：

二叉树中序遍历的迭代算法：

#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); } }

相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。