参考 http://blog.csdn.net/acdnjjjdj… 写了二叉树的遍历,(基本上就是照抄的,囧),抄的时候感慨,stl 真是个好东西啊,另外,在三种次序遍历的实现上,递归的精巧发挥的淋漓尽致啊,还有就是非递归的遍历,设计真的好巧妙
#include <iostream> #include <queue> #include <stack> using namespace std; class Tree { public: char data; Tree *left; Tree *right; void create(Tree *&node); void preOrderVisit(Tree *node); void inOrderVisit(Tree *node); void lastOrderVisit(Tree *node); void levelOrderVisit(Tree *node); void notRecursionPreOrderVisit(Tree *node); void notRecursionInorderVisit(Tree *node); void notRecursionLastOrderVisit(Tree *node); }; void Tree::create(Tree *&node) { char ch; cin>>ch; if (ch == '0') { node = NULL; } else { node = new Tree(); node->data = ch; create(node->left); create(node->right); } } void Tree::preOrderVisit(Tree *node) { if (node) { cout<<node->data<<' '; preOrderVisit(node->left); preOrderVisit(node->right); } } void Tree::inOrderVisit(Tree *node) { if (node) { inOrderVisit(node->left); cout<<node->data<<' '; inOrderVisit(node->right); } } void Tree::lastOrderVisit(Tree *node) { if (node) { lastOrderVisit(node->left); lastOrderVisit(node->right); cout<<node->data<<' '; } } void Tree::levelOrderVisit(Tree *node) { if ( ! node) { return; } queue<Tree *> q; q.push(node); while ( ! q.empty()) { Tree *tmp = q.front(); cout<<tmp->data<<' '; q.pop(); if (tmp->left) { q.push(tmp->left); } if (tmp->right) { q.push(tmp->right); } } } void Tree::notRecursionPreOrderVisit(Tree *node) { stack<Tree *> s; Tree *t = node; while (!s.empty() || t) { if (t) { cout<<t->data<<' '; s.push(t); t = t->left; } else { t = s.top(); s.pop(); t = t->right; } } } void Tree::notRecursionInorderVisit(Tree *node) { stack<Tree *> s; Tree *t = node; while (!s.empty() || t) { if (t) { s.push(t); t = t->left; } else { t = s.top(); s.pop(); cout<<t->data<<' '; t = t->right; } } } void Tree::notRecursionLastOrderVisit(Tree *node) { stack<Tree *> s; Tree *t = node; Tree *pre = NULL; while(!s.empty() || t) { while (t) { s.push(t); t = t->left; } t = s.top(); if (t->right==NULL || t->right==pre) { cout<<t->data<<' '; pre = t; t = NULL; s.pop(); } else { t = t->right; } } } int main() { Tree *t = NULL; t->create(t); t->preOrderVisit(t); cout<<endl; t->inOrderVisit(t); cout<<endl; t->lastOrderVisit(t); cout<<endl; t->levelOrderVisit(t); cout<<endl; t->notRecursionPreOrderVisit(t); cout<<endl; t->notRecursionInorderVisit(t); cout<<endl; t->notRecursionLastOrderVisit(t); cout<<endl; return 0; }
输入输出
124005003600700 1 2 4 5 3 6 7 4 2 5 1 6 3 7 4 5 2 6 7 3 1 1 2 3 4 5 6 7 1 2 4 5 3 6 7 4 2 5 1 6 3 7 4 5 2 6 7 3 1