所谓二叉树的遍历，是指按照某条搜索路径访问树中的每个结点，使得每个结点均被访问依次，而且仅被访问一次。
由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）和后序（LRN）三种遍历算法。其中，序指的是根结点在何时被访问。
typedef int ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
1 先序遍历（PreOrde）
如果二叉树为空，什么也不做。否则：
1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。
对应的递归算法如下：
void PreOrder(BiTree T) {
if (T != NULL) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
2 中序遍历（InOrder）
如果二叉树为空，什么也不做。否则：
1）中序遍历左子树；
2）访问根结点；
3）中序遍历右子树。
对应的递归算法如下：
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
3 后序遍历（PostOrder）
如果二叉树为空，什么也不做。否则：
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根结点。
对应的递归算法如下：
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏的情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。
4 递归算法和非递归算法的转换
可以借助栈，将二叉树的递归遍历算法转换为非递归算法。
1）先序遍历的非递归算法：
void PreOrder2(BiTree T) {
BiTNode *stack[MAXSIZE] = {NULL};
int top = -1;
BiTNode *p = T, *q;
stack[++top] = T; //根结点入栈
while (top > -1) {//栈不为空时循环
p = stack[top--];//退栈
visit(p);//访问p
if (p->rchild) {//如果右孩子不为空，进栈
stack[++top] = p->rchild;
}
if (p->lchild) {//如果左孩子不为空，进栈
stack[++top] = p->lchild;
}
}
}
2）中序遍历的非递归算法
先扫描（并非访问）根结点的所有左结点并将它们一一进栈。然后出栈一个结点p（显然p没有左孩子或者左孩子结点均已访问过），则访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。
void inOrder2(BiTree T) {
BiTNode *stack[MAXSIZE];
BiTNode *p = T;
int top = -1;
while (p || top > -1) { //栈不空或p不空时循环
if (p) {//p不为空时，进栈
stack[++top] = p;
p = p->lchild;//先把所有左子树进栈
} else {
p = stack[top--];//p为空时，出栈一个到p
visit(p);//访问p
p = p->rchild;//往右子树走
}
}
}
3）后序遍历的非递归算法
在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一结点时，不能立即访问，要先遍历其左子树，此时根结点进栈。当其左子树遍历完再搜索到该根结点时，还是不能访问，还需遍历其右子树，所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到该根结点时，才能被访问。
因此，设立一个状态标志变量tag：tag=0时，结点暂不能访问；tag=1时，结点可以被访问。
其次，设立两个堆栈S1，S2，S1保存结点，S2保存结点的状态标志变量tag。S1和S2共用一个栈顶指针。
设T是指向根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，另p=T；
（1）第一次经过根结点p，不访问；p进栈S1，tag赋值0，进栈S2，p=p->Lchilrd。
（2）若p不为空，转（1），否则，取状态标志tag。
（3）若tag=0，对栈S1，不访问，不出栈；修改S2栈顶元素值（tag赋1），取S1栈顶元素的右子树，即p=S1[top]->Rchilrd，转（1）；
（4）若tag=1，S1退栈，访问该节点；直到栈空为止。
void posOrder2(BiTNode *T) {
BiTNode *S1[MAXSIZE], *p = T;
int S2[MAXSIZE], top = -1;
if (T == NULL) {
printf("Tree is Empty!\n");
} else {
do {
while (p != NULL) {//若p不为空，一直扫描左子树
S1[++top] = p;//第一次经过根结点p，不访问；p进栈S1
S2[top] = 0;//tag赋值0,进栈S2
p = p->lchild;
}
if (S2[top] == 0) {//若tag=0,对栈S1，不访问，不出栈
p = S1[top]->rchild;//取S1栈顶元素的右子树
S2[top] = 1;//修改S2栈顶元素值（tag赋1）
} else {//如果tag=1
p = S1[top--];//S1退栈
visit(p);//访问该结点
p = NULL;//使循环继续进行不至于死循环
}
} while (top > -1);
}
}
测试代码：
int main() {
BiTree A = (BiTNode *) malloc(sizeof(BiTNode));
BiTree B = (BiTNode *) malloc(sizeof(BiTNode));
BiTree C = (BiTNode *) malloc(sizeof(BiTNode));
BiTree D = (BiTNode *) malloc(sizeof(BiTNode));
BiTree E = (BiTNode *) malloc(sizeof(BiTNode));
A->data = 1;
B->data = 2;
C->data = 3;
D->data = 4;
E->data = 5;
A->lchild = B;
A->rchild = C;
B->lchild = D;
B->rchild = NULL;
C->lchild = NULL;
C->rchild = E;
D->lchild = NULL;
D->rchild = NULL;
E->lchild = NULL;
E->rchild = NULL;
// PreOrder(A);
// InOrder(A);
// PostOrder(A);
// PreOrder2(A);
// inOrder2(A);
// posOrder2(A);
return 0;
}
5 层次遍历
要进行层次遍历需要借助一个队列。先将二叉树根结点入队，然后出队，访问该结点，如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。
image
二叉树的层次遍历算法如下：
void levelorderTraverse(BiTNode *T) {
BiTNode *Queue[MAXSIZE], *p = T;
int front = -1, rear = -1;
if (p != NULL) {
Queue[++rear] = p;//根结点入队
while (front < rear) {
p = Queue[++front];
visit(p);
if (p->lchild != NULL) {
Queue[++rear] = p->lchild;//左结点入队
}
if (p->rchild != NULL) {
Queue[++rear] = p->rchild;//右结点入队
}
}
}
}
网友评论