C說話完成二叉樹遍歷的迭代算法。本站提示廣大學習愛好者:(C說話完成二叉樹遍歷的迭代算法)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話完成二叉樹遍歷的迭代算法正文
本文實例講述了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法式算法設計的進修有必定的自創價值。