介绍

非递归需要用到栈数据结构。

• 前序遍历：根节点-》左孩子-》右孩子。 将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则访问该节点并将该节点压栈（将该节点的地址压栈），继而遍历其左子树；循环执行，直到当前节点为空时，取栈顶元素并访问其右子树，再重复如上操作，直至遍历节点的指针为空且栈也为空；
• 中序遍历：左孩子-》根节点-》右孩子。将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则将该节点压栈并访问其左子树，循环执行，直至当前节点为空时，取栈顶元素访问并弹栈，然后访问其右子树，再重复如上操作，直至遍历节点的指针为空在且栈也为空。（中序遍历和前序遍历的不同在于：前序遍历是入栈的同时访问结点，而中序遍历是出栈的同时访问结点）；
• 后序遍历：左孩子-》右孩子-》根节点。将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则将该节点压栈并访问其左子树，循环执行，直至当前节点为空时，取栈顶元素，判断其右子树是否为空且是否已遍历，如果非空且为遍历则访问其右子树，再将其压栈遍历其左子树；如果右子树为空或已遍历则访问该结点并弹栈，同时设置标记指针记录遍历过的点（用于判断右子树是否已遍历），再将遍历指针置空（下次遍历直接取栈顶元素），直至遍历节点的指针为空且栈也为空。

代码

前序遍历

void preorder(BiTree T){
//二叉树的非递归前序遍历 
	stack<BiTree> s;
	while(T||!s.empty()){
	//当前结点或栈不为空时执行该循环 
		if(T!=NULL){//当前结点不为空时 
			cout<<T->data;//访问当前结点信息 
			s.push(T);//将该节点的地址压栈 
			T=T->lchild;//遍历左孩子 
		}
		else{//当前结点为空时 
			T=s.top();//取栈顶的元素 
			s.pop();//弹栈 
			T=T->rchild;//遍历右孩子 
		}
	}
}

中序遍历

void inorder(BiTree T){
//二叉树的非递归中序遍历 
	stack<BiTree> s;
	while(T||!s.empty()){
	//当前结点或栈不为空时执行该循环 
		if(T!=NULL){//当前结点不为空时
			s.push(T);//将该节点的地址压栈
			T=T->lchild;//遍历左孩子
		}
		else
		{
			T=s.top();//取栈顶的元素
			s.pop();//弹栈
			cout<<T->data;//访问当前结点信息
			T=T->rchild;//遍历右孩子			
		}
	}
}

后序遍历

void postorder(BiTree T){
//二叉树的非递归后序遍历 
	BiTree r=NULL;
	stack<BiTree> s;
	while(T||!s.empty()){
		if(T!=NULL){//当结点不为空时，该结点压栈并遍历其左子树 
			s.push(T);
			T=T->lchild;
		}
		else{//当左子树结点为空时，取栈顶元素进行右子树的遍历， 
			T=s.top();
			if(T->rchild!=NULL&&T->rchild!=r){
			//右子树不为空且右子树没有被遍历过 
				T=T->rchild;
				s.push(T);//将该结点压栈，遍历其左子树 
				T=T->lchild;
			}
			else{//右子树为空或已遍历则取栈顶元素访问该结点的信息 
				s.pop();
				cout<<T->data;
				r=T;//标记遍历过的点，用于判断右子树是否已遍历 
				T=NULL;//遍历结点的指针置空，下次遍历直接取栈中的值 
			}
		}
	}
}