前言

本文通过代码加注释的方法向大家介绍——1.递归的先、中,后序遍历算法;2.非递归的先、中,后序遍历算法;3.层次遍历算法

递归的遍历算法

  1. 递归的先序遍历算法
//易于理解,先根结点,再左孩子,再右孩子的顺序。
void PreOrder(BiTree){
	if(T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

  1. 递归的中序遍历算法
//易于理解,先左孩子,再根结点,再右孩子的顺序。
void InOrder(BiTree){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

  1. 递归的先序遍历算法
//易于理解,先左孩子,再右孩子,再根结点的顺序。
void PostOrder(BiTree){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

非递归的遍历算法

  1. 中序遍历
//二叉树的中序遍历,需要的参数是一棵二叉树
void InOrder2(BiTree T){
/*这里初始化的这个栈是该算法思想的核心,因为中序遍历是每遇到一棵树,先访问该树的左子树,所以就要使用一个具备“后进先出”特性的数据结构去存放每遍历到的一个结点。每遇到一个结点,先放进栈里,然后去找该节点的左子树,在左子树中,把该左子树的根结点也先放进栈里,然后去找这棵左子树的根结点的左子树,这么一层一层找下去。当栈里的结点出栈时,意味着,该访问此结点了*/
InitStack(S)	//初始化一个栈,用于存放结点
BiTree p = T;	//T是一个地址,所以这里p是一个指针,用于接下来的遍历
while(p||!IsEmpty(S)){	//p所指的地址有数据或者栈里还有数据时循环
	if(p){	//p所指的地址由数据的情况
		Push(S,p);
		p=p->lchild;
	}	
	else{	//p所指地址无数据,但是栈里还有数据时的情况
		Pop(S,p)	
		visit(p)
		p=p->rchild;
	}
}
}
  1. 先序遍历
//二叉树的先序遍历,需要的参数是一棵二叉树
void PreOrder2(BiTree T){
/*先序遍历是每遇到一棵树,先访问该树的根结点。所以与中序遍历有所不同,每次遇到一个结点,先访问该结点,然后让该结点入栈。这里入栈的结点与中序遍历不同,是已经访问过的结点,入栈的目的是等到对该结点的左子树遍历完之后,能够查找到该结点的右子树并去进行遍历。*/
InitStack(S)	//初始化一个栈,用于存放结点
BiTree p = T;	//T是一个地址,所以这里p是一个指针,用于接下来的遍历
while(p||!IsEmpty(S)){	//p所指的地址有数据或者栈里还有数据时循环
	if(p){	//p所指的地址由数据的情况
		visit(p);
		Push(S,p);
		p=p->lchild;
	}	
	else{	//p所指地址无数据,但是栈里还有数据时的情况
		Pop(S,p)	
		p=p->rchild;
	}
}
}

/*小总结:非递归的中序遍历与先序遍历思想很类似,都是通过一个栈去实现对已遍历过的结点的一个保存,方便后面进行完该结点的左子树的查找之后能够找到该结点的右子树进行接下来的遍历,栈的特性完美契合了本算法,是个很好的选择。*/
  1. 后序遍历
//二叉树的后序遍历,需要的参数是一棵二叉树
void PostOrder2(BiTree T){
/*后序遍历也需要使用“后进先出”的栈来实现对结点的保存,但是后序遍历与先、中序遍历的思想差异较大,因为他是先访问左右孩子,最后访问根节点。那么每次经过一个结点就需要把这个结点先放进栈里面(等到他的左右孩子都遍历完,他才能被访问)。然后去找他的左孩子,对于以左孩子为根节点的子树也采用这样的策略,就这样左孩子做孩子地找下去……当不存在左孩子了之后,就要访问此时处于栈顶的结点(注意,是访问,不是出栈!因为该结点本身还没被访问过,要等到最后要访问自己了才能够出栈!)查找到右子树,去遍历右子树,最后轮到这些个根结点,出栈并访问。*/
InitStack(S)	//初始化一个栈,用于存放结点
BiTree p = T;	//T是一个地址,所以这里p是一个指针,用于接下来的遍历
r=NULL;	    //这里定义了一个辅助指针,用于判定该结点是否被访问过。
while(p||!IsEmpty(S)){	//p所指的地址有数据或者栈里还有数据时循环
	if(p){	//p所指的地址由数据的情况
		Push(S,p);
		p=p->lchild;
	}	
	else{	//p所指地址无数据,但是栈里还有数据时的情况
		GetTop(S,p)	//如上面所说,仅是访问,不是出栈	
		if(p->rchild&&p->rchild!=r)	
		{
			p=p->rchild;
			Push(S,p);
			p=p->lchild;
		}
		else{
			pop(S,p);
			visit(p);
			r=p;
			p=NULL;
		}
	}
}
}
/*补充——为何要设置辅助指针r:因为你往上一层结点返回的时候,可能是从左孩子返回的,也可能是从右孩子返回的,从左孩子返回时表示该根结点的右孩子结点还没有遍历,当然了此时r指向的也不是右孩子结点,就会去遍历右孩子结点为根节点的子树。那么遍历完这棵右子树后在往上返回就是从右孩子往上返回了,要是不加这个r你就不知道右孩子遍历完了,你又会去再遍历这个右孩子,没完没了,所以说要加一个辅助指针告诉计算机右子树遍历完了,我就是从右子树过来的,你该继续往上返回了。【其实对于该算法,你找一个二叉树,用该算法思想对其进行一次后序遍历自己试试就很明显了,也非常好理解了。】*/
  1. 层次遍历
//二叉树的层次遍历,需要的参数是一棵二叉树
void LevelOrder(BiTree T){
/*层次遍历就不使用“后进先出”的栈来实现对结点的保存了,而是使用“先进先出”的队列结构来保存结点,所以他和先中后序遍历是由根本上不同的,但是也非常简单好理解。层次遍历就是从上往下从左到右一层一层去遍历每一个结点,从根结点开始,访问完该结点,访问左右孩子结点,通过下面的入队出队操作,依附于队列“先进先出”的特性,很容易实现层次遍历。*/
InitQueue(Q)	//初始化一个队列,用于存放结点
BiTree p;	//T是一个地址,所以这里p是一个指针,用于接下来的遍历
EnQueue(Q,T);	//开始时把树的根结点T放进队列
while(!IsEmpty(Q)){	//只要队列里有结点,就进行循环
	DeQueue(Q,p)
	visit(p);
	if(p->lchild!=MULL)
		EnQueue(Q,p->lchild);
	if(p->rchild!=NULL)
		EnQueue(Q,p->rchild);
	}	
}