二叉树的遍历算法

递归版本

先序遍历：

void preorder (BTNode *p) {
    if (p != NULL) {
        Visit(p);
        preorder(p->lchild);
        preorder(p->rchild);
    }
}

中序遍历：

void inorder (BTNode *p) {
    if (p != NULL) {
        preorder(p->lchild);
        Visit(p);
        preorder(p->rchild);
    }
}

后序遍历：

void postorder (BTNode *p) {
    if (p != NULL) {
        preorder(p->lchild);
        Visit(p);
        preorder(p->rchild);
    }
}

非递归版本

先序遍历：

void preoderNonrecursion (BTNode *bt) {
    if (bt != NULL) {
        BTNode *Stack [maxSize];
        int top = -1;
        BTNode *p = NULL;
        Stack[++top] = bt;

        while (top != -1) {
            p = Stack[top--];
            Visit(p);
            if (p.rchild != NULL) { //由于栈先进后出的特性，右子树先进栈
                Stack[++top] = p->rchild;
            }
            if (p->lchild != NULL) {
                Stack[++top] = p-lchild;
            }
        }
    }
}

中序遍历：

void inorderNonrecursion (BTNode *bt) {
    if (bt != NULL) {
        BTNode *Stack[maxSize];
        int top = -1;
        BTNode *p = bt;
        
        while (top != -1 || p != NULL) {
            while (p != NULL) {
                Stack[++top] = p;
                p = p->lchild;
            }
            if(top != -1) {
                p = Stack[top--];
                Visit(p);
                p = p->rchild;
            }
        }
    }
}

后序遍历：

//逆后续遍历序列是先序遍历对左右子树遍历顺序交换的结果。
//即先求先序遍历对左右子树遍历顺序交换的序列，再将该序列逆序即可得到后续遍历序列
void postorderNonrecursion (BTNode *bt) {
    if (bt != NULL) {
        BTNode *Stack1[maxSize], *Stack2[maxSize];
        int top1 = -1, top2 = -1;
        BTNode *p = NULL;
        Stack1[++top1] = bt;
        while (top1 != -1) {
            p = Stack1[top1--];
            Stack2[++top2] = p;
            //注意下面两个if语句的进栈顺序与先序遍历的区别，左右孩子的入栈顺序相反
            if (p->lchild != NULL) {
                Stack1[++top1] = p->lchild;
            }
            if (p->rchild != NULL) {
                Stack1[++top1] = p->rchild;
            }
        }
        while (top2 != -1) {
            //出栈序列即为后序遍历序列
            p = Stack2[top2--];
            Visit(p);
        }
    }
}

层次遍历：

void level (BTNode *p) {
    if (p != NULL) {
        int front = 0, rear = 0;
        BTNode *que[maxSize];
        BTNode *q = NULL;
        
        rear = (rear + 1) % maxSize;
        que[rear] = p;
        while (front != rear) {
            front = (front + 1) % maxSize;
            q = que[front];
            Visit(q);
            if (q->lchild != NULL) {
                rear = (rear + 1) % maxSize;
                que[rear] = q->lchild;
            }
            if (q->rchild != NULL) {
                rear = (rear + 1) % maxSize;
                que[rear] = q->rchild;
            }
        }
    }
}