二叉树的常见遍历方式有三种
// 二叉树的二叉链表存储结构
typedef struct BiNode
{
int data;
struct BiNode *left_child, *right_child;
} BiNode, *BiTree
- 前序遍历
// 二叉树的前序遍历
void pre_traversal(BiTree t)
{
if (t == NULL)
{
return;
}
printf("%d", t->data);
pre_traversal(t->left_child);
pre_traversal(t->right_child);
}
- 中序遍历
// 二叉树的中序遍历
void in_traversal(BiTree t)
{
if (t == NULL)
{
return;
}
in_traversal(t->left_child);
printf("%d", t->data);
in_traversal(t->right_child);
}
- 后序遍历
// 二叉树的后序遍历
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在左在右都不能确定。
