두 갈래 나무의 역행 (역귀와 비역귀)

전순, 중순, 후순의 귀속과 비귀속, 그리고 차원을 두루 훑어보는 것을 포함한다
앞순서 비귀속 (1) 노드가 비어 있지 않을 때, 이 노드 데이터에 접근한 후, 이 노드는 창고에 들어가서 저장한 다음, 왼쪽 트리 노드에 접근해야 한다
(2) 창고의 노드가 창고를 나갈 때 이 노드와 왼쪽 트리 노드가 이미 접근을 마쳤음을 설명하고 창고를 나간 후 오른쪽 트리에 들어가 접근한다
중차순 비귀속
(1) 앞의 순서와 비귀속적이고 노드 데이터에 접근할 시기가 다르기 때문에 창고를 나갈 때 방문하면 된다
후순 비귀속
(1) 이 노드의 데이터가 접근되었는지 여부를 기록하는 표지가 필요하다
(2) 창고가 비어 있지 않고 창고 꼭대기 요소의 tag가 1이면 창고 요소의 좌우 트리에 접근이 완료되었습니다. 다음은 창고 꼭대기 요소 데이터에 접근해야 합니다
차원: 대기열로 실현 (1) 먼저 루트 노드를 대열에 넣기
(2) 대기열이 비어 있지 않을 때 줄을 서서 노드 데이터에 접근한 다음 노드의 왼쪽 트리(존재), 오른쪽 트리(존재)를 각각 입장시킨다
구현 코드는 다음과 같습니다.

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct TreeNode
{
	int data;
	int tag;		//0 ,1 ( )
	TreeNode *lChid;
	TreeNode *rChidl;

	TreeNode(int key, TreeNode *pLeft, TreeNode *pRight):data(key),tag(0), lChid(pLeft), rChidl(pRight) {}
};

void createTree(TreeNode **root);

// 
void preOrderTraverse(TreeNode *root);
void preOrderTraverse_not_recursive(TreeNode *root);

// 
void inOrderTraverse(TreeNode *root);
void inOrderTraverse_not_recursive(TreeNode *root);

// 
void postOrderTraverse(TreeNode *root);
void postOrderTraverse_not_recursive(TreeNode *root);

// 
void levelOrderTraverse(TreeNode *root);

int main()
{
	TreeNode *root = NULL;
	createTree(&root);

	// 
	cout << " :";
	preOrderTraverse(root);		
	cout << "
 :";
	preOrderTraverse_not_recursive(root);	
	cout << endl;

	// 
	cout << "
 :";
	inOrderTraverse(root);
	cout << "
 :";
	inOrderTraverse_not_recursive(root);
	cout << endl;

	// 
	cout << "
 :";
	postOrderTraverse(root);
	cout << "
 :";
	postOrderTraverse_not_recursive(root);
	cout << endl;

	// 
	cout << "
 :";
	levelOrderTraverse(root);
	cout << endl;

	// ( )
	system("pause");
	return 0;
}

void createTree(TreeNode **root)
{
	TreeNode *node7 = new TreeNode(7, NULL, NULL);
	TreeNode *node6 = new TreeNode(6, NULL, NULL);
	TreeNode *node5 = new TreeNode(5, node7, NULL);
	TreeNode *node4 = new TreeNode(4, NULL, NULL);
	TreeNode *node3 = new TreeNode(3, node5, node6);
	TreeNode *node2 = new TreeNode(2, NULL, node4);
	*root = new TreeNode(1, node2, node3);
}

/***********************************************************************/
//FUNCTION: 
void preOrderTraverse(TreeNode *root)
{
	if (root != NULL)
	{
		cout << root->data << "  ";
		preOrderTraverse(root->lChid);
		preOrderTraverse(root->rChidl);
	}
}

void preOrderTraverse_not_recursive(TreeNode *root)
{
	stack<TreeNode*> stk;
	while (root != NULL || !stk.empty())
	{
		while (root != NULL)			
		{
			cout << root->data << "  ";	
			stk.push(root);				
			root = root->lChid;			
		}

		if (!stk.empty())				
		{
			root = stk.top();
			stk.pop();					
			root = root->rChidl;	
		}
	}
}

/***********************************************************************/
//FUNCTION: 
void inOrderTraverse(TreeNode *root)
{
	if (root != NULL)
	{
		inOrderTraverse(root->lChid);
		cout << root->data << "  ";
		inOrderTraverse(root->rChidl);
	}
}

void inOrderTraverse_not_recursive(TreeNode *root)
{
	stack<TreeNode*> stk;
	while (root != NULL || !stk.empty())
	{
		while (root != NULL)			
		{
			stk.push(root);				
			root = root->lChid;		
		}

		if (!stk.empty())				
		{
			root = stk.top();
			stk.pop();					
			cout << root->data << "  ";	
			root = root->rChidl;	
		}
	}
}

/***********************************************************************/
//FUNCTION: 
void postOrderTraverse(TreeNode *root)
{
	if (root != NULL)
	{
		postOrderTraverse(root->lChid);
		postOrderTraverse(root->rChidl);
		cout << root->data << "  ";
	}
}

void postOrderTraverse_not_recursive(TreeNode *root)
{
	stack<TreeNode*> stk;
	while (root != NULL || !stk.empty())
	{
		while (root != NULL)			
		{
			stk.push(root);				
			root = root->lChid;			
		}

		while (!stk.empty() && stk.top()->tag == 1)
		{
			root = stk.top();
			cout << root->data << "  ";
			stk.pop();
		}

		if (!stk.empty())				
		{
			root = stk.top();
			root->tag = 1;					
			root = root->rChidl;		
		}
		else
			root = NULL;
	}
}

/***********************************************************************/
//FUNCTION: 
void levelOrderTraverse(TreeNode *root)
{
	queue<TreeNode*> qQueue;
	if (root != NULL)
	{
		qQueue.push(root);

		while (!qQueue.empty())
		{
			root = qQueue.front();
			cout << root->data << "  ";
			qQueue.pop();

			if (root->lChid != NULL)
				qQueue.push(root->lChid);

			if (root->rChidl != NULL)
				qQueue.push(root->rChidl);
		}
	}
}