二叉树
这次是一个二叉树的算法。我首先列出二叉树类的代码清单：
templateclass tree;template class node { friend class tree ;public: typedef T value_type;protected: node* _l = nullptr; node* _r = nullptr; value_type _v;public: const node& left() const { if(!_l) throw std::runtime_error("Null Pointer"); return *_l; } const node& right() const { if(!_r) throw std::runtime_error("Null Pointer"); return *_r; } node& left() { if(!_l) _l = new node(); return *_l; } node& left(const value_type& v) { if(!_l) _l = new node(v); else _l->_v = v; return *this; } bool hasl() const { return _l; } bool hasr() const { return _r; } node& right() { if(!_r) _r = new node(); return *_r; } node& right(const value_type& v) { if(!_r) _r = new node(v); else _r->_v = v; return *this; } node() { } node(const value_type& v) : _v(v) { } ~node() { if(_l) delete _l; if(_r) delete _r; } const value_type& val() const { return _v; } value_type& val() { return _v; } node& val(const value_type& v) { _v = v; return *this; }};template class tree {public: typedef T value_type; typedef node node_type;protected: node_type _root;public: tree() { } tree(const value_type& v) : _root(v) { } node_type& root() { return _root; } const node_type& root() const { return _root; } node_type& root(const value_type& v) { _root._v = v; return _root; }};int main(){ tree stree; stree.root("A").left("B") .left().left("C").right("D") .right().left("E").right("F") .left().right("G");}
main 中所建造的二叉树有这样的结构：
A / B / \ C D / \ E F \ G
递归先根遍历
不用脑想就随手打出来三行代码：
templatevoid traverse(node const & t){ cout << t.val() << endl; if(t.hasl()) traverse(t.left()); if(t.hasr()) traverse(t.right());}
它的输出结果是：
ABCDEGF
用栈来模拟递归遍历
大家知道“栈”这个东西，在操作系统概念或者x86汇编的概念上也有一个，是ESP到EBP所划分的一段内存。在这个栈上面保存着现场（Scenery），所谓现场，包含两样东西：一是局部变量，二是程序返回的位置。所以在这里，我们用一个pair<node*, int>来表示现场。每一次循环，从栈顶恢复局部变量loc.first和返回位置loc.second：
templatevoid traverse_non_recursive_1(node const & _t){ typedef pair const *, int> scenery; stack s; s.push(scenery(&_t, 0)); while(!s.empty()) { scenery& loc = s.top(); node const & t = *loc.first; switch(loc.second++) { case 0: cout << t.val() << endl; if(t.hasl()) s.push(make_pair(&t.left(), 0)); break; case 1: if(t.hasr()) s.push(make_pair(&t.right(), 0)); break; case 2: s.pop(); break; } }}
尾递归优化
右子树的递归if(t.hasr()) traverse(t.right())，因为在其后已经没有任何语句了，所以属于尾递归。在尾递归发生的情况下，对当前局部变量的修改不会对代码执行产生任何影响（因为已经没有什么可执行的代码了）。所以，我们直接覆盖栈顶，而不是将下一次调用所需的变量和返回位置压栈。这样可以节省内存空间，并且节约代码：
templatevoid traverse_non_recursive_2(node const & _t){ typedef pair const *, int> scenery; stack s; s.push(scenery(&_t, 0)); while(!s.empty()) { scenery& loc = s.top(); node const & t = *loc.first; switch(loc.second++) { case 0: cout << t.val() << endl; if(t.hasl()) s.push(make_pair(&t.left(), 0)); break; case 1: if(t.hasr()) s.top() = make_pair(&t.right(), 0); else s.pop(); break; } }}
0-1优化
0-1优化是我创造的名词（笑），因为这种优化方案在只有两个代码段（或者说只发生一次递归，或者第二次递归为尾递归而被优化了）的时候可以适用。如果我们在执行途中打印出栈内所有element.second（返回位置），我们只可能见到两种情况：
1 1 1 1 ... 1 1 1 01 1 1 1 ... 1 1
也就是说，除开栈顶元素，其余元素只可能为1。原因是：在将新元素压栈之前，当前栈顶必然已经不为0（loc.second++处）。所以，我们只需记录最后一个元素即可。这里用bt（backtrace）标记栈顶是否是回溯回来的而不是新压的：
templatevoid traverse_non_recursive_3(node const & _t){ stack const *> s; s.push(&_t); bool bt = false; while(!s.empty()) { node const & t = *s.top(); if(!bt) { cout << t.val() << endl; if(t.hasl()) { bt = false; s.push(&t.left()); } else bt = true; } else { if(t.hasr()) { bt = false; s.top() = &t.right(); } else { s.pop(); bt = true; } } }}