二叉树的遍历

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

前序遍历

ABDECF

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
typedef struct TreeNode *Tree;//二叉树节点
void preorder(Tree t) { //前序遍历
    if (t == NULL) {//空树
        return;//返回
    }
    printf("%c", t->element);//访问根节点
    preorder(t->left);//访问左子树
    preorder(t->right);//访问右子树
}
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    Tree f = (Tree) malloc(sizeof(struct TreeNode));
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = f;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    f->left = NULL;
    f->right = NULL;
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';
    preorder(a);
}

中序遍历

DBEAC

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
void inorder(struct TreeNode *t) { //中序遍历
    if (t == NULL) {//空树
        return;//返回
    }
    inorder(t->left);//访问左子树
    printf("%c", t->element);//访问根节点
    inorder(t->right);//访问右子树
}
typedef struct TreeNode *Tree;//二叉树节点
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = NULL;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    inorder(a);
    return 0;
}

后序遍历

DEBCA

#include <stdio.h>
#include <stdlib.h>
typedef char E;//元素类型
struct TreeNode {
    E element;//节点元素
    struct TreeNode *left;  //左子树
    struct TreeNode *right; //右子树
};
typedef struct TreeNode *Tree;//二叉树节点
void backorder(Tree root){
    if(root == NULL) return;
    backorder(root->left);
    backorder(root->right);
    printf("%c", root->element);
}
int main(void) {
    Tree a = (Tree) malloc(sizeof(struct TreeNode));
    Tree b = (Tree) malloc(sizeof(struct TreeNode));
    Tree c = (Tree) malloc(sizeof(struct TreeNode));
    Tree d = (Tree) malloc(sizeof(struct TreeNode));
    Tree e = (Tree) malloc(sizeof(struct TreeNode));
    a->element= 'A';
    b->element= 'B';
    c->element= 'C';
    d->element= 'D';
    e->element = 'E';
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = NULL;
    c->right = NULL;
    d->left = NULL;
    d->right = NULL;
    e->left = NULL;
    e->right = NULL;
    backorder(a);
}