/*二叉树的先序遍历非递归算法目标遍历的二叉树:1/ \2   4/ \3   5	待输出结果为1,2,3,5,41.首先得用上面定义的结构体把这颗树表示出来2.表示出这颗树后在调用二叉树的先序遍历非递归算法
*/

#include <iostream>
using namespace std;
# define maxSize 10
//树结点的结构体，存储的是int整型的数据
typedef struct BTNode{int data;struct BTNode *lchild;struct BTNode *rchild;
}BTNode;/*二叉树的先序遍历非递归算法目标遍历的二叉树:1/ \2   4/ \3   5	待输出结果为1,2,3,5,41.首先得用上面定义的结构体把这颗树表示出来2.表示出这颗树后在调用二叉树的先序遍历非递归算法
*/void createBTree(BTNode *&p)
{	/*生成这颗树，这里就是直接按照二叉树的样子来逐一生成p做为根结点(root)*/p = (BTNode*)malloc(sizeof(BTNode));p->data = 1;BTNode *n2, *n3, *n4, *n5 ;//分别对应存储元素2，4，3，5的4个结点n2 = (BTNode*)malloc(sizeof(BTNode));n3 = (BTNode*)malloc(sizeof(BTNode));n4 = (BTNode*)malloc(sizeof(BTNode));n5 = (BTNode*)malloc(sizeof(BTNode));n2->data = 2;n3->data = 4;n4->data = 3;n5->data = 5;p->lchild = n2;p->rchild = n3;n2->lchild = n4;n2->rchild = n5;n3->lchild = n3->rchild = NULL;n4->lchild = n4->rchild = NULL;n5->lchild = n5->rchild = NULL;
}
void preorderNonrecursion(BTNode *p){if (p != NULL){BTNode *q;BTNode *stack[maxSize];			//定义一个栈int top = -1;					//初始栈stack[++top] = p;				//根结点入栈while (top != -1)				//如果栈非空则循环{q = stack[top--];			//栈顶结点出栈cout << q->data <<endl;if (q->rchild != NULL)      //一定保证q的右孩子先入栈{stack[++top] = q->rchild;}if (q->lchild != NULL)		//这样出栈的时候左孩子在右孩子之前先访问{stack[++top] = q->lchild;}}}
}int main()
{BTNode *p;createBTree(p);preorderNonrecursion(p);return 0;
}