二叉树的迭代法前序遍历的两种方法

二叉树的前序遍历的顺序为：中左右。如下图，打印顺序为:
’3’->’9’->’15’->’4’->’7’->’1’->’20’->’0’

方法一：模拟递归法实现的递归过程

递归的过程为：
(1)每次在将左节点入栈之前，打印节点数据，直到最左节点为空。如打印节点’3’，然后再压入栈中；打印左节点’9’，然后再压入栈中。
(2)取出栈中的节点最左结点’15’，并将其从栈中删除；
(3)查找取出节点的右边节点,为空则重复(2),不为空，将右节点压入栈中，重复(1)。

代码如下：

void PreOrder(TreeNode* node)
{
    
	stack<TreeNode*> st;
	TreeNode* current = node;
	st.push(current);
	while (!st.empty()){
    
		/*第一步*/
		while (current){
    
			cout << current->data << " ";//打印数据
			current = current->leftChild;//每次都指向左节点
			if (current) st.push(current);//左节点不空，就压入栈中
		}
		/*第二步，取出节点并删除*/
		current = st.top();
		st.pop();
		/*第三步，处理右节点*/
		if (current->rightChild){
    
			current = current->rightChild;
			st.push(current);
		}
		else{
    
			current = nullptr;
		}
	}
}

方法二：按照“中左右”的遍历顺寻，将父节点和左右子节点入栈

从栈中取出节点，打印节点，删除节点；将取出节点的右节点’20’压入栈中，然后将左节点’9’压入栈中。并不断进行上述操作。此方法能行的原因是总是父节点先打印数据。
代码如下：

void PreOrder(TreeNode* node)
{
    
	stack<TreeNode*> st;
	TreeNode* current = node;
	st.push(current);

	while (!st.empty()){
    
		current = st.top();
		st.pop();

		std::cout << current->data << " ";
		if (current->rightChild) st.push(current->rightChild);
		if (current->leftChild) st.push(current->leftChild);
	}
}

测试代码及打印结果，生成的树如上所示：

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

using namespace std;

class TreeNode
{
    
public:
	int data;
	TreeNode *leftChild;
	TreeNode *rightChild;

	TreeNode();
	TreeNode(int _data) :data(_data), leftChild(nullptr), rightChild(nullptr){
    }
	TreeNode(int _data, TreeNode* _leftChild, TreeNode* _rightChild)
		:data(_data), leftChild(_leftChild), rightChild(_rightChild){
    }
};
void PreOrder1(TreeNode* node)
{
    
	stack<TreeNode*> st;
	TreeNode* current = node;
	st.push(current);
	while (!st.empty()){
    
		/*第一步*/
		while (current){
    
			cout << current->data << " ";//打印数据
			current = current->leftChild;//每次都指向左节点
			if (current) st.push(current);//左节点不空，就压入栈中
		}
		/*第二步，取出节点并删除*/
		current = st.top();
		st.pop();
		/*第三步，处理右节点*/
		if (current->rightChild){
    
			current = current->rightChild;
			st.push(current);
		}
		else{
    
			current = nullptr;
		}
	}
}
void PreOrder2(TreeNode* node)
{
    
	stack<TreeNode*> st;
	TreeNode* current = node;
	st.push(current);

	while (!st.empty()){
    
		current = st.top();
		st.pop();

		std::cout << current->data << " ";
		if (current->rightChild) st.push(current->rightChild);
		if (current->leftChild) st.push(current->leftChild);
	}
}
int main()
{
     
	TreeNode node1(3), node2(9), node3(15), node4(7), node5(20), node6(1), node7(0), node8(4);
	node1.leftChild = &node2;
	node1.rightChild = &node5;

	node2.leftChild = &node3;
	node2.rightChild = &node4;

	node3.rightChild = &node8;

	node4.rightChild = &node6;

	node5.rightChild = &node7;

	std::cout << "方法一前序遍历打印：";
	PreOrder1(&node1);
	cout << endl;
	std::cout << "方法二前序遍历打印：";
	PreOrder2(&node1);
	cout << endl;

	system("pause");
	return 0;
}

以上就是二叉树前序遍历的迭代非递归法的两种实现。

如果有疑问，欢迎评论区下方留言；本人水平有限 ，如有错误，也欢迎在评论区下方批评指正。若是喜欢本文，就帮忙点赞吧！