【数据结构】二叉树的先中后序遍历与层序遍历

二叉树是递归定义的数据结构。

1. 先序遍历

根左右（NLR）

先序遍历也叫深度优先遍历。

先序遍历结果：A B D E C F G

解析：根据先序遍历根左右的遍历顺序。首先遍历A，然后遍历B，再遍历C，但是遍历到B的时候又会遵循根左右的原则，遍历了D和E。当遍历到C的时候，同样遵循根左右的原则，遍历了F和G。

先序遍历操作过程如下：

1. 若二叉树为空，则什么也不做；
2. 若二叉树非空：

• 访问根结点；
• 先序遍历左子树；
• 先序遍历右子树。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);  // 访问根结点
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
}

2. 中序遍历

左根右（LNR）

中序遍历结果为：D B E A F C G

解析：根据中序遍历左根右的遍历顺序。首先遍历B，然后遍历A，再遍历C，但是遍历到B的时候又会遵循左根右的原则，遍历了D，然后遍历B和E。当遍历到C的时候，同样遵循左根右的原则，遍历了F，然后是C和G。

中序遍历操作过程如下：

1. 若二叉树为空，则什么也不做；
2. 若二叉树非空：

• 先序遍历左子树；
• 访问根结点；
• 先序遍历右子树。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);  // 递归遍历左子树
        visit(T);  // 访问根结点
        PreOrder(T->rchild);  // 递归遍历右子树
    }
}

3. 后序遍历

左右根（LRN）

中序遍历结果为：D E B F G C A

解析：根据后序遍历左右根的遍历顺序。首先遍历B，然后遍历C，再遍历A，但是遍历到B的时候又会遵循左右根的原则，遍历了D，然后遍历E。当遍历到C的时候，同样遵循左右根的原则，遍历了F，然后是G，最后遍历A。

后序遍历操作过程如下：

1. 若二叉树为空，则什么也不做；
2. 若二叉树非空：

• 先序遍历左子树；
• 先序遍历右子树；
• 访问根结点。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
        visit(T);  // 访问根结点
    }
}

4. 应用

求树的深度。

int treeDepth(BiTree T){
    if(T==NULL){
        return 0;
    }else{
        int l=treeDepth(T->lchild);
        int r=treeDepth(T->rchild);
        return l>r?l+1:r+1;
    }
}

5. 二叉树的层序遍历

层序遍历也叫层次遍历，也叫广度优先遍历。

算法思想：

1. 初始化一个辅助队列。
2. 根结点入队。
3. 若队列非空，则队头结点出队，访问该节点。并将其左、右孩子插入队尾（如果有的话）。
4. 重复3的步骤直至队列为空。

// 二叉树的节点（链式存储）
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 链式队列结点
typedef struct LinkNode{
    BiTNode * data;  // 注意：存指针而不是存结点
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear; // 队头队尾
}LinkQueue;

// 层序遍历
void LevelOrder(BiTree T){
    LinkQueue  Q;
    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);  // 右孩子入队
        }
    }
}