非遞歸二叉樹先序周遊、中序周遊及後序周遊

資料結構定義：

struct Node {
	char val;
	pNode lchild, rchild;
};
           

二叉樹形态：

A
     /   \
    B     C
   / \   / \
  D   E F   G
       / \
      H   I
           

前序周遊：

先判斷節點的指針是否為空，不為空就先通路該結點，然後直接進棧，接着周遊左子樹；為空則要從棧中彈出一個節點來，這個時候彈出的結點就是其父親，然後通路其父親的右子樹，直到目前節點為空且棧為空時，算法結束.

void preVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p = root;
	while (p != NULL || !s.empty()) {
		if (p != NULL) {
			printf("%c ", p->val);
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}
           

中序周遊：

和先序周遊一樣，但在通路節點的順序不一樣，通路節點的時機是從棧中彈出元素時通路，如果從棧中彈出元素，就意味着目前節點父親的左子樹已經周遊完成，這時候通路父親，就是中序周遊.

void midVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p = root;
	while (p != NULL || !s.empty()) {
		if (p != NULL) {
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			printf("%c ", p->val);
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}
           

後序周遊：

後續周遊，首先通路左子樹，把父親節點儲存于棧中，問題是當元素從棧中彈出的時候，我們無法判斷這個時候是該通路其右子樹還是通路父親節點，于是我們就需要一個标記，當通路左子樹時我們把父親節點的标記設為1，表示下一步如果彈出該節點，就通路其右子樹；彈出一個節點時，我們要判斷該節點的标記，如果是1，則通路其右子樹，并把該節點的标記設定成2，表示下一步就通路該節點，然後把該節點繼續入棧，如果是2，那麼表示通路該節點，通路并且丢棄該節點.

void backVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p, q;
	p = root;
	q = NULL;
	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			if (p->rchild == NULL || p->rchild == q)
			{
				printf("%c ", p->val);
				q = p;
				s.pop();
				p = NULL;   //重要  避免死循環
			}
			else
			{
				p = p->rchild;
			}
		}
	}
	cout << endl;
}
           

測試代碼：

#include <iostream>
#include <stack>

using namespace std;

typedef struct Node *pNode;

struct Node {
	char val;
	pNode lchild, rchild;
};

void createBiTree(pNode &T)
{
	char c;
	cin >> c;
	if ('#' == c)
		T = NULL;
	else
	{
		T = new Node;
		T->val = c;
		createBiTree(T->lchild);
		createBiTree(T->rchild);
	}
}

void preVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p = root;
	while (p != NULL || !s.empty()) {
		if (p != NULL) {
			printf("%c ", p->val);
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}

void midVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p = root;
	while (p != NULL || !s.empty()) {
		if (p != NULL) {
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			printf("%c ", p->val);
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}

void backVisitStack(pNode root)
{
	stack<pNode> s;
	pNode p, q;
	p = root;
	q = NULL;
	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			if (p->rchild == NULL || p->rchild == q)
			{
				printf("%c ", p->val);
				q = p;
				s.pop();
				p = NULL;   //重要  避免死循環
			}
			else
			{
				p = p->rchild;
			}
		}
	}
	cout << endl;
}

int main()
{
	Node* root;
	createBiTree(root);
	printf("先序周遊：");
	preVisitStack(root);
	printf("中序周遊：");
	midVisitStack(root);
	printf("後序周遊：");
	backVisitStack(root);
	system("pause");
}
           

測試輸入：ABD##E##CFH##I##G##

測試結果：

前序周遊：  

A B D E C F H I G 

中序周遊： 

D B E A H F I C G 

後序周遊： 

D E B H I F G C A