循环遍历二叉树

本文给出用循环（非递归）方式对二叉树进行前序、中序、后序遍历的 C++ 实现，核心思路是用 std::stack 模拟函数调用栈。

辅助结构与建树

首先定义节点结构，并提供一个递归建树函数用于测试：

struct Node
{
	Node*left;
	Node*right;
	int data;
	Node(){ func; }
};



Node* create(Node*p, int depth)
{
	if (p && depth)
	{
		p->left = new Node;
		p->right = new Node;
		p->data = depth;
		create(p->left, depth - 1);
		create(p->right, depth - 1);


	}
	if (!depth)
	{
		p->left = nullptr;
		p->right = nullptr;
		p->data = depth;

	}

	return p;

}

前序遍历

递归版本 print1 按"根-左-右"顺序输出。循环版本 print2 用栈模拟同样的调用过程：

void print1(Node*p)
{
	if (p)
	{
		cout << p->data << " ";
		print1(p->left);
		print1(p->right);
	}
}

void print2(Node*head)//利用stack 模拟函数调用过程 来遍历
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);
			cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();

			if (pp->right && pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);
			cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();

			if (pp->right
				&& pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}

}



int main()
{

	Node* head = new Node;
	create(head, 2);

	head->data = 10;
	head->left->data = 6;
	head->right->data = 14;

	head->left->left->data = 4;
	head->left->right->data = 8;

	head->right->left->data = 12;
	head->right->right->data = 16;

	print1(head);//递归遍历
	cout << endl;
	print2(head);//循环遍历




	system("pause");
	return 0;
}

中序遍历

循环中序遍历同样借助栈，按"左-根-右"顺序依次输出节点值：

void print2(Node*head)
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);
		//	cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
			cout << pp->data << " ";

			if (pp->right && pp != head  )
			{

				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);

			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
			cout << pp->data << " ";
			if (pp->right&& pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}

}

后序遍历

循环后序遍历按"左-右-根"顺序输出，根节点最后单独输出：

void print2(Node*head)
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);

			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
			if (pp->right && pp != head  )
			{

				cout << pp->right->data << " ";
			}
			if ( pp != head)
			cout << pp->data << " ";
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();

			if (pp->right&& pp != head)
			{
				cout << pp->right->data << " ";
			}
			cout << pp->data << " ";
			s.pop();
		}

	}
	cout << head->data << " ";
}