循环遍历二叉树

本文给出用循环（非递归）方式对二叉树进行前序、中序、后序遍历的 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 << " ";
                }