二叉树的递归遍历实现起来比较简单，而且代码简洁；而非递归遍历则不那么简单，我们需要利用另一种数据结构---栈来实现。二叉树的遍历又可以分为前序、中序和后序三种，它们是按照根结点在遍历时的位置划分的，前序遍历则根结点先被遍历，中序则根结点在左右叶子节点之间被遍历，后序则是根结点最后被遍历。三种非递归遍历中，前序和中序都不是太复制，而后序遍历则相对较难。

一、前序遍历

        我们这里前序遍历按照“根-左-右”的顺序来遍历。这里按照”递归--非递归“的次序来研究，之后的几种亦是如此。

        1、递归的实现：

void travel_3(node* r) {
		if (r != NULL) {
			cout << r->key << ' ';
			travel_3(r->left);
			travel_3(r->right);
		}
	}

        2、非递归的实现：

        非递归的实现中肯定是需要用到循环结构的，前序遍历又要求先根后左然后右，所以我们肯定是首先需要遍历左节点的，但是遍历左节点之后还需要我们继续遍历右节点，而且右节点也有可能还有左子树需要先遍历。于是乎，这里我们需要一个栈来保存我们已经遍历完的节点，在遍历完左右的左节点之后，再将栈里保存的节点出栈，然后再遍历节点的右子树，然后将右子树的节点带入循环中，这样比较底层的节点会靠近栈顶，也会被先出栈，如此就可以实现非递归的前序遍历。具体步骤如下：

        ①先输出节点的值，然后将节点入栈

        ②然后判断节点的左子节点是否为空，如果不为空，则继续循环①；如果为空，则证明这一条线路上的节点值已经被遍历完了，则跳出循环进行出栈操作，只要栈不为空，则节点出栈，并让节点等于他的右子节点，继续进行①号循环

        ③直到所有节点都已经出栈，且循环到节点为空，则遍历结束

	void travel_4(node* r) {
		if (r != NULL) {
			stack<node*> s;
			while (r != NULL || !s.empty()) {
				while (r != NULL) {
					cout << r->key << ' ';
					s.push(r);
					r = r->left;
				}

				if (!s.empty()) {
					r = s.top();
					s.pop();
					r = r->right;
				}
			}
		}
	}

二、中序遍历

        中序遍历与前序遍历有些类似，只是按照“左-根-右”的顺序遍历。

        1、递归的实现：

	void travel_1(node* r) {
		if (r != NULL) {
			travel_1(r->left);
			cout << r->key << ' ';
			travel_1(r->right);
		}
	}

        2、非递归的实现：

        非递归的实现中序遍历跟前序遍历的非递归实现差不多，差别只在于输出节点的key值位置变了，不再是在取左子节点之前输出，而是在出栈之后才输出节点的值，这样会从最左边的节点开始输出，然后再是根节点和右边的节点。

        ①直接将节点入栈

        ②然后判断节点的左子节点是否为空，如果不为空，则继续循环①；如果为空，则证明这一条线路上的已经都入栈了，则跳出循环进行出栈操作，只要栈不为空，则节点出栈，输出节点的值，并让节点等于他的右子节点，继续进行①号循环

        ③直到所有节点都已经出栈，且循环到节点为空，则遍历结束

	void travel_2(node* r) {
		if (r != NULL) {
			stack<node*> s;
			while (r != NULL || !s.empty()) {
				while (r != NULL) {
					s.push(r);
					r = r->left;
				}

				if (!s.empty()) {
					r = s.top();
					s.pop();
					cout << r->key << ' ';
					r = r->right;
				}
			}
		}
	}

三、后序遍历

        后序遍历的递归实现跟之前的没什么差别，但是非递归实现则比较复杂。

        1、递归的实现：

	void travel_5(node* r) {
		if (r != NULL) {
			travel_5(r->left);
			travel_5(r->right);
			cout << r->key << ' ';
		}
	}

        2、非递归的实现：

        这里我们依旧需要用到栈，但是我们需要保证根结点一定要在左右子节点遍历完之后才被遍历。如何保证这一点呢？可以像下面这样做：

        ①拿到一个节点，先将其入栈，则它一定在比较靠栈底的地方，比较晚出栈

        ②如果这个节点没有左右子节点，则我们大可以直接输出它

        ③如果这个节点有左或者右子节点或者两者都有，那么我们可以再将其左右子节点也入栈

        ④在出栈的时候，我们会发现左右子节点总是在根结点之前出栈，也就是在其之前被遍历，但是还是有问题

        ⑤我们需要在出栈判断到底是只有左节点还是只有右节点或者是两者都有或者是都没有。如果我们发现它左右子节点都为空，则大可直接输出它；或者，如果发现前一个出栈的节点是它的左节点或者右子节点，则也可以输出它。否则，表示这个节点是一个新的节点，我们需要先将其左右子节点入栈。

	void travel_6(node* r) {
		if(r==NULL){
			return;
		}
		stack<node*> s;
		node* current_pointer;
		node* last_pointer; //记录前一次循环的指针

		s.push(r); //先将根结点压栈

		while (!s.empty()) {
			current_pointer = s.top(); //每次循环都要更新当前指针为新的栈顶

			if ((current_pointer->left == NULL && current_pointer->right == NULL)
					|| (last_pointer != NULL
							&& (last_pointer == current_pointer->left
									|| last_pointer == current_pointer->right))) {

				cout << current_pointer->key << ' ';
				s.pop();
				last_pointer = current_pointer;
			} else {
				if (current_pointer->right != NULL) {
					s.push(current_pointer->right);
				}
				if (current_pointer->left != NULL) {
					s.push(current_pointer->left);
				}
			}
		}
	}

完整代码：

struct node {
	int key;
	node* parent;
	node* left;
	node* right;
	node() :
			key(0), parent(), left(NULL), right(NULL) {
	}

	node(int k) :
			key(k), parent(), left(NULL), right(NULL) {
	}

	~node() {
		key = 0;
	}
};

class bintree {

public:
	node* root;

	bintree() :
			root() {
	}

	~bintree() {
		//做一些清理的工作，防止内存泄露
		delete_tree(root);
	}

	void delete_tree(node* p) {
		if (p != NULL) {
			node* right = p->right;
			node* left = p->left;
			delete_tree(left);
			delete p;
			delete_tree(right);
			p = NULL;
			right = NULL;
			left = NULL;
		}
	}

	

	/*
	 * 中序遍历，递归方式
	 */
	void travel_1(node* r) {
		if (r != NULL) {
			travel_1(r->left);
			cout << r->key << ' ';
			travel_1(r->right);
		}
	}

	void travel_1() {
		travel_1(root);
		cout << endl;
	}

	/*
	 * 中序遍历，非递归方式
	 */
	void travel_2(node* r) {
		if (r != NULL) {
			stack<node*> s;
			while (r != NULL || !s.empty()) {
				while (r != NULL) {
					s.push(r);
					r = r->left;
				}

				if (!s.empty()) {
					r = s.top();
					s.pop();
					cout << r->key << ' ';
					r = r->right;
				}
			}
		}
	}

	void travel_2() {
		travel_2(root);
		cout << endl;
	}

	/*
	 * 前序遍历，递归方式
	 */

	void travel_3(node* r) {
		if (r != NULL) {
			cout << r->key << ' ';
			travel_3(r->left);
			travel_3(r->right);
		}
	}
	void travel_3() {
		travel_3(root);
		cout << endl;
	}

	/*
	 * 前序遍历，非递归方式
	 */
	void travel_4(node* r) {
		if (r != NULL) {
			stack<node*> s;
			while (r != NULL || !s.empty()) {
				while (r != NULL) {
					cout << r->key << ' ';
					s.push(r);
					r = r->left;
				}

				if (!s.empty()) {
					r = s.top();
					s.pop();
					r = r->right;
				}
			}
		}
	}

	void travel_4() {
		travel_4(root);
		cout << endl;
	}

	/*
	 * 后序方式，递归
	 */

	void travel_5(node* r) {
		if (r != NULL) {
			travel_5(r->left);
			travel_5(r->right);
			cout << r->key << ' ';
		}
	}

	void travel_5() {
		travel_5(root);
		cout << endl;

	}

	/*
	 * 后序方式，非递归
	 */

	void travel_6(node* r) {
		if(r==NULL){
			return;
		}
		stack<node*> s;
		node* current_pointer;
		node* last_pointer; //记录前一次循环的指针

		s.push(r); //先将根结点压栈

		while (!s.empty()) {
			current_pointer = s.top(); //每次循环都要更新当前指针为新的栈顶

			if ((current_pointer->left == NULL && current_pointer->right == NULL)
					|| (last_pointer != NULL
							&& (last_pointer == current_pointer->left
									|| last_pointer == current_pointer->right))) {

				cout << current_pointer->key << ' ';
				s.pop();
				last_pointer = current_pointer;
			} else {
				if (current_pointer->right != NULL) {
					s.push(current_pointer->right);
				}
				if (current_pointer->left != NULL) {
					s.push(current_pointer->left);
				}
			}
		}
	}

	void travel_6() {
		travel_6(root);
		cout << endl;
	}

};

【算法导论】二叉树的前中后序非递归遍历实现