二叉树遍历

二叉树的遍历方式有多种，名字天花乱坠，没必要去死记，不管是前序，后序等等，关键以双亲结点为中心，所谓前序还是后序实质上就是一个双亲结点和左右子结点为一个小的集体中双亲结点是先遍历还是后遍历，然后许多这样的小集体不停递归的过程，知道了这点，根据不同的遍历方式，首先认准双亲结点啥时候遍历，然后找好先后关系，很容易就能够画出来遍历结果，下面这些情况也就迎刃而解了

前序遍历：先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历：先中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树

后序遍历：从左到右先叶子后结点的方式遍历访问左和右子树，最后访问根结点

层序遍历：从树的第一层也就是根结点开始访问，从上而下逐层便利，同一层从左到右

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

typedef struct tree {
//    char data;
    int data;
    struct tree *left;
    struct tree *right;
}tree;

tree* CreateBTree(){
    tree *t;
//    char ch;
    int ch;
    scanf_s(“%d”, &ch);
    printf(“\n”);
    if (ch == 0)
        t = NULL;
    else {
        t = (tree *)malloc(sizeof(tree));
        if (!t)
            exit(-1);
        t->data = ch;
        printf(“Node %d left child: “, t->data);
        t->left = CreateBTree();
        printf(“Node %d right child: “, t->data);
        t->right = CreateBTree();
    }
    return t;
}

int First(tree *n){
    if (!n)
        return 0;
    else {
        printf(“%d “, n->data);
        First(n->left);
        First(n->right);
    }
    return 0;
}

int Last(tree *n){
    if (!n)
        return 0;
    else {
        Last(n->left);
        Last(n->right);
        printf(“%d” , n->data);
    }
    return 0;
}

int Middle(tree *n){
    if (!n)
        return 0;
    else {
        Middle(n->left);
        printf(“%d” , n->data);
        Middle(n->right);
    }
    return 0;
}

int main(){
    tree *p;
    p = (tree *)malloc(sizeof(tree));
    if (!p)
        exit(-1);
    printf(“Create BTree !\n”);
    printf(“Please input root node: “);
    p = CreateBTree();
    printf(“\nFirst Visit BTree: “);
    First(p);
    printf(“\nLast Visit BTree: “);
    Last(p);
    printf(“\nMiddle Visit BTree: “);
    Middle(p);
//    printf(“Step Visit BTree: “);
//    Step(p);
    return 0;
}