二叉树的遍历

什么是遍历？

按照某种规则把所欲结点都访问一遍

树的遍历

先/中/后遍历：基于树的递归特性确定的次序规则

二叉树的递归特性

1. 要么是个空二叉树
2. 要么就是由“根结点+左子树+右子树”组成的二叉树

先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）

C语言代码实现

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

void InitTree(BiTree T,int m){
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = m;
    T->lchild = NULL;
    T->rchild = NULL;
}

void visit(BiTree T){
    printf("%d\t",T->data);
}

//前序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}