本章主要通过运用递归与非递归方法分别对二叉树进行遍历

主要分先序遍历、中序遍历、后序遍历以及层次遍历四种情况进行讨论

目录

一. 先序遍历

1.1 递归法

1.2 非递归法

二. 中序遍历 

2.1 递归法

2.2 非递归法 

三. 后序遍历

3.1 递归法

3.2 非递归法

四. 层次遍历 

一. 先序遍历

1.1 递归法

  根据二叉树的递归特性，先序遍历二叉树的递归过程如下：

（1）访问根结点

（2）先序遍历左子树

（3）先序遍历右子树 

void preorder(BiTree t){if(t!=NULL){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}
} 

1.2 非递归法

从上面的算法中可以看出，先序遍历的递归过程简短而易于理解。依照递归算法执行过程中递归工作栈的状态变化状况可以直接写出相应的非递归算法。非递归算法中借助栈来完成整个遍历过程。算法的基本步骤如下：

（1）当前指针指向根结点。

（2）若结点不为空，访问该结点。

（3）若结点右孩子不为空，则右孩子进栈。

（4）当前指针指向结点左孩子重复步骤（2）~（3），直至左孩子为空。

（5）依次退栈，当前指针指向出栈结点。

（6）若栈非空或当前指针非空，继续步骤（2），直至结束。

由此可以写出先序遍历的非递归算法： 

void PreOrder(BiTree t){BiTree stack[MAX],q;int top=0,i;for(i=0;idata);if(q->rchild!=NULL){stack[top++]=q->rchild;}if(q->lchild!=NULL){q=q->lchild;}else if(top>0){q=stack[--top];}else{q=NULL;}}
}

二. 中序遍历 

2.1 递归法

  中序遍历二叉树的递归过程如下： 

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

void inorder(BiTree t){if(t!=NULL){inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);}
}

2.2 非递归法 

  同样也可以利用栈来实现中序遍历的非递归算法，算法的基本步骤如下：

（1）当前指针指向根结点。

（2）当前指针进栈，当前指针指向其左孩子。

（3）重复步骤（2），直至左孩子为空。

（4）依次退栈，输出当前指针所指结点。

（5）将当前指针指向右孩子。

（6）若栈非空或当前指针非空，执行步骤（2），直至结束。 

void InOrder(BiTree t){BiTree stack[MAX],p;int top=0,i;for(i=0;i0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];printf("%c",p->data);p=p->rchild;}
}

三. 后序遍历

3.1 递归法

  后序遍历二叉树的递归过程如下：

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点 

void postorder(BiTree t){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);}
}

3.2 非递归法

后序遍历的非递归算法比先序和中序的非递归算法复杂一些。按照后序遍历的过程，在遍历左子树之前，就要将根结点的地址保存在栈中，以便能在左子树遍历完成之后，从栈中弹出根结点地址，通过根结点走到右子树；但因为还没有遍历右子树，所以类似的，在遍历右子树之前，必须再次将根结点压入栈中，在遍历完右子树后，才能访问它。由于一个结点要进栈、出栈两次，就要对它是第一次进栈还是第二次进栈的情况加以区分。可以通过为结点增加标志位或与刚刚访问的结点相比较的方法，达到判断该结点是否应该访问的目的。

  因此要引入一个标志栈flag[max]，对应结点的标志为0，表明左子树遍历，标志为1，表明右子树遍历。后序遍历二叉树的非递归算法步骤如下：

（1）当前指针指向根结点。

（2）当前指针不为空，进栈，所对应标志为0，当前指针指向其左孩子，重复直至左孩子为空。

（3）判断栈顶元素的标志，若为1，则依次退栈，输出结点，直至标志为0。

（4）若栈顶元素的标志为0，将当前指针指向栈顶元素的右孩子，并置标志为1，进栈；若当前指针为空，则退栈，输出结点，直至标志为0。

（5）若栈非空或当前指针非空，执行步骤（2），直至结束。 

void PostOrder(BiTree t){BiTree stack[MAX],q;int i,top=0,flag[MAX];for(i=0;ilchild;}else{while(top){if(flag[top-1]==0){q=stack[top-1];q=q->rchild;flag[top-1]=1;break;}else{q=stack[--top];printf("%c",q->data);}}}if(top==0) break;}	
}

四. 层次遍历 

二叉树的层次遍历是指从二叉树的根结点开始，从上往下逐层遍历，同一层中的结点按从左往右的顺序访问。层次遍历需要借助一个辅助队列，利用队列先进先出的特性，存放访问过的结点，以便下一层继续按照结点的左右次序访问它们的孩子。

层次遍历的基本步骤如下：

（1）从根结点开始，访问根结点，并进行入队操作。

（2）若队不为空，就进行出队操作，访问出队结点的左右孩子，并入队。继续循环，直至队列为空。

层次遍历二叉树的算法如下：

void CcOrder(BiTree t){BiTree p;SqQueue qlist,*q;q=&qlist;q->front=0;q->rear=0;p=t;if(p!=NULL){printf("%c",p->data);q->data[q->rear]=p;q->rear=(q->rear+1)%MAX;while(q->front!=q->rear){p=q->data[q->front];q->front=(q->front+1)%MAX;if(p->lchild!=NULL){printf("%c",p->lchild->data);q->data[q->rear]=p->lchild;q->rear=(q->rear+1)%MAX;}if(p->rchild!=NULL){printf("%c",p->rchild->data);q->data[q->rear]=p->rchild;q->rear=(q->rear+1)%MAX;}}}
}