我们知道二叉树的遍历主要有，前序，中序，后续，我们常用递归的方式进行实现，而我们都知道能用递归函数实现，都可以用数据结构栈进行实现。

下面我们就用栈的数据结构来处理二叉树的前序遍历：

BinaryTree.h

#pragma once
struct BinaryTreeNode
{
	int m_value;
	struct BinaryTreeNode* m_left;
	struct BinaryTreeNode* m_right;
};
//二叉树结点的创建
struct BinaryTreeNode* CreateBinaryNode(int value);

//二叉树结点的连接
void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild);

//二叉树结点的打印
void PrintBinaryNode(const struct BinaryTreeNode*node);


//前序非递归打印二叉树
void PreorderTraverseTreeNonRec(BinaryTreeNode* pRoot);

//二叉树结点的销毁
void DestroyBinaryNode(struct BinaryTreeNode*node);

//整个二叉树的销毁
void DestroyBinary(struct BinaryTreeNode*node);

BinaryTree.cpp如下所示：

#include"BinaryTree.h"
#include<cstdio>
#include<queue>
#include<stack>
//二叉树结点的创建
struct BinaryTreeNode* CreateBinaryNode(int value)
{
	struct BinaryTreeNode*pNode = new BinaryTreeNode();
	pNode->m_value = value;
	pNode->m_left = nullptr;
	pNode->m_right = nullptr;

	return pNode;
}

//二叉树结点的连接
void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild)
{
	if (Parent != NULL)
	{
		Parent->m_left = lchild;
		Parent->m_right = rchild;
	}
}

//二叉树结点的打印
void PrintBinaryNode(const struct BinaryTreeNode*node)
{
	if (node != nullptr)
	{
		printf("node value is[%d]\n",node->m_value);
	}
	else
	{
		printf("this node is nullptr\n");
	}
}


//前序遍历二叉树非递归 采用栈的数据结构
void PreorderTraverseTreeNonRec(BinaryTreeNode* pRoot)
{
	std::stack<struct BinaryTreeNode*> stacknode;
	if (pRoot != nullptr)
	{
		stacknode.push(pRoot);
		while (!stacknode.empty())
		{
			BinaryTreeNode* tmp = stacknode.top();
			//打印值
			printf("value is[%d]\n",tmp->m_value);
			stacknode.pop();
			if (tmp->m_right) 
			{ 
				stacknode.push(tmp->m_right);
			}
			if (tmp->m_left)  
			{
				stacknode.push(tmp->m_left);
			}
		}
	}
}





//二叉树结点的销毁
void DestroyBinary(struct BinaryTreeNode*node)
{
	if (node != nullptr)
	{
		struct BinaryTreeNode*pleft = node->m_left;
		struct BinaryTreeNode*pright = node->m_right;

		delete node;
		node = nullptr;

		if (pleft != nullptr)
		{
			DestroyBinary(pleft);
		}

		if (pright != nullptr)
		{
			DestroyBinary(pright);
		}


	}
}

测试代码如下：

int main(int argc, char*argv[])
{
	struct BinaryTreeNode* node1 = CreateBinaryNode(10);
	struct BinaryTreeNode* node2 = CreateBinaryNode(6);
	struct BinaryTreeNode* node3 = CreateBinaryNode(14);
	struct BinaryTreeNode* node4 = CreateBinaryNode(4);
	struct BinaryTreeNode* node5 = CreateBinaryNode(8);
	struct BinaryTreeNode* node6 = CreateBinaryNode(12);
	struct BinaryTreeNode* node7 = CreateBinaryNode(16);


	ConnectBinaryNode(node1, node2, node3);
	ConnectBinaryNode(node2, node4, node5);
	ConnectBinaryNode(node3, node6, node7);

	//非递归先序遍历
	printf("preorder no rec start\n");
	PreorderTraverseTreeNonRec(node1);



	

	return 0;
}