遞歸版本

先序遍歷：

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) { //由于棧先進(jìn)后出的特性，右子樹先進(jìn)棧
                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;
            }
        }
    }
}

后序遍歷：

//逆后續(xù)遍歷序列是先序遍歷對(duì)左右子樹遍歷順序交換的結(jié)果滤淳。
//即先求先序遍歷對(duì)左右子樹遍歷順序交換的序列廷痘，再將該序列逆序即可得到后續(xù)遍歷序列
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;
            //注意下面兩個(gè)if語句的進(jìn)棧順序與先序遍歷的區(qū)別式廷，左右孩子的入棧順序相反
            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;
            }
        }
    }
}