• 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点使得每个结点被访问且仅被访问一次

前序遍历

若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树

中序遍历

若二叉树为空，则空操作返回，否则从根结点开始（并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树
（把二叉树拍成饼，从左到右的顺序）

后序遍历

若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点
（拔完叶子，把根铲了）

层次遍历

一层一层的遍历

二叉树的创建和前序遍历

#include <stdio.h>
#include <stdlib.h>


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

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiTree(BiTree *T) {
    char c;
    scanf("%c",&c);

    if ( ‘ ‘ == c ){
        *T = NULL;
    } else {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

void visit(char c,int level) {
    printf("%c 位于第 %d 层 \n",c,level);
}
// 前序遍历二叉树
void PreOrderTraverse(BiTree T, int level) {
    if ( T ) {
        visit(T->data,level);
        PreOrderTraverse(T->lchild,level+1);
        PreOrderTraverse(T->rchild,level+1);
    }
}
int main()
{
    int level = 1;
    BiTree T;
    T = NULL;

    CreateBiTree(&T);
    PreOrderTraverse(T,level);
    return 0;
}

二叉树的遍历