二叉树的遍历

二叉树的常见遍历方式有三种

// 二叉树的二叉链表存储结构
typedef struct BiNode
{
    int data;
    struct BiNode *left_child, *right_child;
} BiNode, *BiTree

1. 前序遍历

// 二叉树的前序遍历
void pre_traversal(BiTree t)
{
    if (t == NULL)
    {
        return;
    }
    printf("%d", t->data);
    pre_traversal(t->left_child);
    pre_traversal(t->right_child);
}

2. 中序遍历

// 二叉树的中序遍历
void in_traversal(BiTree t)
{
    if (t == NULL)
    {
        return;
    }
    in_traversal(t->left_child);
    printf("%d", t->data);
    in_traversal(t->right_child);
}

3. 后序遍历

// 二叉树的后序遍历
void post_traversal(BiTree t)
{
    if (t == NULL)
    {
        return;
    }
    post_traversal(t->left_child);
    post_traversal(t->right_child);
    printf("%d", t->data);
}

二叉树

对于上图所示的二叉树
前序遍历结果为：0、1、3、4、2、5、6
中序遍历结果为：3、1、4、0、5、2、6
后序遍历结果为：3、4、1、5、6、2、0

已知前序遍历结果和中序遍历结果可以确定一棵二叉树
已知后续遍历结果和中序遍历结果可以确定一棵二叉树
已知前序和后序遍历结果不能确定一棵二叉树

比如已知前序遍历结果为ABC，后序遍历结果为CBA，这样只能知道A为根节点，B在第二层，C在第三层，具体B在左在右与C在左在右都不能确定。