@TOC

先序遍历（根–左--右）

递归法

void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);				//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}

非递归法

void PreOrder(BiTree T){
	InitStack(S);				//使用栈存储二叉树的节点
	BiTree p = T;				//p为遍历二叉树的指针
	while(p || !IsEmpty(S)){	//二叉树不为空或栈不空是继续循环
		if(p != NULL){
			vist(p)				//访问拍p
			Push(S,p);			//p节点入栈
			p = p->lchild;		//继续向左遍历
		}
		else{
			Pop(S,p);			//p出栈
			p = p->rchild;		//转向右子树遍历
		}
	}
}

中序遍历（左–根--右）

递归法

void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);		//递归遍历左子树
		visit(T);				//访问根节点
		InOrder(T->rchild);		//递归遍历右子树
	}
}

非递归法

void InOrder(BiTree T){
	InitStack(S);				//使用栈存储二叉树的节点
	BiTree p = T;				//p为遍历二叉树的指针
	while(p || !IsEmpty(S)){	//二叉树不为空或栈不空是继续循环
		if(p != NULL){
			Push(S,p);			//p节点入栈
			p = p->lchild;		//继续向左遍历
		}
		else{
			Pop(S,p);			//p出栈
			visit(p);			//访问p
			p = p->rchild;		//转向右子树遍历
		}
	}
}

后序遍历（左–右--根）

递归法

void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);		//递归遍历左子树
		PostOrder(T->rchild);		//递归遍历右子树
		visit(T);					//访问根节点
	}
}

非递归法

void PostOrder(BiTree T){
	InitStack(S);					//使用栈存储二叉树的节点
	BiTree p = T;					//p为遍历二叉树的指针
	BiTree r = NULL;				//记录最近访问的节点
	while(p || !IsEmpty(S)){		//二叉树不为空或栈不空是继续循环
		if(p != NULL){
			Push(S,p);				//p节点入栈
			p = p->lchild;			//继续向左遍历
		}
		else{
			GetTop(S,p);			//读取栈顶节点，不出栈
			if(p->rchild && p->rchild != r){	//右子树存在，且未被访问
				p = p->rchild;
				Push(S,p);						//p节点入栈
				p = p->lchild;					//转左遍历
			}
			else{
				Pop(S,p);						//p出栈
				visit(p);						//访问p
				r = p;							//记录最近一次访问的节点
				p = NULL;
			}
		}
	}
}

层序遍历

void LevelOrder(BiTree T){
	InitQueue(Q);				//使用队列存储二叉树节点
	BiTree p;
	EnQueue(Q,T);				//根节点入队
	while(!IsEmpty(Q)){			//队列不空继续循环
		DeQueue(Q,p);			//队头节点出队
		vist(p);				//访问队头节点
		if(p->lchild != NULL){
			EnQueue(Q,p->lchild);	//左孩子入队
		}
		if(p->rchild != NULL){
			EnQueue(Q,p->rchild);	//右孩子入队
		}
	}			
}