순서

제목:
각각 귀속과 비귀속의 방식으로 두 갈래 나무의 선차순, 중차순, 후차순을 누적합니다!

두 갈래 나무 노드 구조

struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;

	TreeNode(int v) :val(v), left(NULL), right(NULL){}
};

먼저 순서대로 두루 다니다.

차례로 실현되다

/* */
void preOrderRecur(TreeNode *tree)
{
	if (!tree)
		return;

	cout << tree->val << "\t";
	preOrderRecur(tree->left);
	preOrderRecur(tree->right);
}

비귀속 실현

/* */
void preOrderUnRecur(TreeNode *tree)
{
	if (!tree)
		return;

	stack<TreeNode *> stk;
	/* */
	stk.push(tree);
	while (!stk.empty())
	{
		TreeNode *tmp = stk.top();
		cout << tmp->val << "\t";
		stk.pop();

		/* ， */
		if (tmp->right)
			stk.push(tmp->right);
		if (tmp->left)
			stk.push(tmp->left);
	}//while
}

중순으로 두루 다니다.

차례로 실현되다

/* */
void inOrderRecur(TreeNode *tree)
{
	if (!tree)
		return;

	inOrderRecur(tree->left);
	cout << tree->val << "\t";
	inOrderRecur(tree->right);
}

비귀속 실현

/* */
void inOrderUnRecur(TreeNode *tree)
{
	if (!tree)
		return;

	stack<TreeNode *> stk;
	TreeNode *cur = tree;
	while (!stk.empty() || cur)
	{
		if (cur)
		{
			stk.push(cur);
			cur = cur->left;
		}//if
		else{
			cur = stk.top();
			stk.pop();
			cout << cur->val << "\t";
			cur = cur->right;
		}//else
	}//while
}

후순이 두루 다니다

차례로 실현되다

/* */
void postOrderRecur(TreeNode *tree)
{
	if (!tree)
		return;

	postOrderRecur(tree->left);
	postOrderRecur(tree->right);
	cout << tree->val << "\t";
}

비귀속 실현 1

/* 1*/
void postOrderRecur1(TreeNode *tree)
{
	if (!tree)
		return;

	/* */
	stack<TreeNode *> stk1;
	stack<TreeNode *> stk2;

	stk1.push(tree);
	while (!stk1.empty())
	{
		TreeNode *tmp = stk1.top();
		stk1.pop();
		if (tmp->left)
			stk1.push(tmp->left);
		if (tmp->right)
			stk1.push(tmp->right);

		stk2.push(tmp);
	}//while

	while (!stk2.empty())
	{
		cout << stk2.top()->val << "\t";
		stk2.pop();
	}//while
}

비귀속 실현 방식 2

/* 2*/
void postOrderRecur2(TreeNode *h)
{
	if (!h)
		return;

	/* ，h */
	stack<TreeNode *> stk;
	stk.push(h);
	TreeNode *tmp;
	while (!stk.empty())
	{
		/*tmp */
		tmp = stk.top();
		if (tmp->left && h != tmp->left && h != tmp->right)
		{
			stk.push(tmp->left);
		}//else
		else if (tmp->right && h != tmp->right)
		{
			stk.push(tmp->right);
		}//elif
		else
		{
			cout << tmp->val << "\t";
			stk.pop();
			h = tmp;
		}//else
	}//while
}

전체 프로그램 GitHub 웹 주소