云的小站

// 二叉树的链式存储结构描述

typedef struct BitTNode {
    int data;                           // 数据域
    struct BiTNode *lchild,*rchild;     // 左、右孩子指针
}BiTNode,*BiTNode;

1. 先序遍历，根->左->右

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

2. 中序遍历，左->根->右

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

3. 后序遍历，左->右->根

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

4. 二叉树层次遍历

void LevelOrder(BiTree T){
    InitQueue(Q);                   // 初始化辅助队列
    BiTree p;
    EnQueue(Q,T);                   // 将根节点入队
    while(!IsEmpty(Q)){             // 队列不空则循环
        DeQueue(Q,p);               // 队头节点出队
        visit(p);                   // 访问出队节点
        if(p->lchild!= NULL){
            EnQueue(Q,p->lchild);   // 左子树不为空，则左子树根节点入队
        }
        if(p->rchild!= NULL){       // 右子树不为空，则右子树根节点入队
            EnQueue(Q,p->rchild);
        }
    }