二叉树的前序序列是ABDEGHCFIJ 中序序列为DBGEHACIFJ
根据前序序列ABDEGHCFIJ, 可以确定A是根结点.
中序序列DBGEH A CIFJ里以A为中心, DBGEH是A的左子树, CIFJ是A的右子树.
A
/ \
DBGEH CIFJ
前序序列ABDEGHCFIJ里B紧跟A之后, B是A的左孩子.
中序序列DBGEHACIFJ里D排在最前, D之后是B, 预计D没有左子树,也没有右子树,
并且D是B的左孩子.
A
/ \
B CIFJ
/ \
D GEH
前序序列ABDEGHCFIJ里E跟在B后面, 预计E是B的右孩子.
中序序列DBGEHACIFJ里E的左边是G, 而右边是H, 预计E的左孩子是G, 右孩子是H,
再次观察前序序列ABDEGHCFIJ里的EGH这种顺序可以确定,E的左右孩子就是G和H.
A
/ \
B CIFJ
/ \
D E
/ \
G H
前序序列ABDEGHCFIJ里的CFIJ, C排在最前,
中序序列DBGEHACIFJ里的C在A的后面, 可以确定C是A的右孩子.
A
/ \
B C
/ \ \
D E IFJ
/ \
G H
前序序列ABDEGHCFIJ里F跟在C的后面, F会是C的左孩子或者右孩子,
而F后面跟着的是IJ, 预计I和J属于F的子树.
中序序列DBGEHACIFJ里C之后是F, 而F的左边是I, 右边是J, I跟在C的后面,
可以确定F是C的右孩子, I和J是F的左右孩子.
二叉树示意图:
A
/ \
B C
/ \ \
D E F
/ \ / \
G H I J
后序序列是 D G H E B I J F C A
C语言测试程序
测试结果:
创建二叉树,输入前序扩展序列: ABD##EG##H##C#FI##J##
前序遍历序列: A B D E G H C F I J
中序遍历序列: D B G E H A C I F J
后序遍历序列: D G H E B I J F C A
#include<
stdio.h>
#include<
stdlib.h>
typedef struct Node
{
char data;
struct Node *lchild;
struct Node *rchild;
}Bitree;
//用"前序遍历"算法创建二叉树
void CreateBiTree(Bitree **bt)
{
char s;
scanf("%c",&s); //
输入数据 if(s=='#') //'#'是空节点
*bt=NULL;
else
{
*bt=(Bitree *)malloc(sizeof(Bitree));
(*bt)->data=s;
CreateBiTree(&((*bt)->lchild));
CreateBiTree(&((*bt)->rchild));
}
}
//前序遍历
void preOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
printf("%c ",ptr->data);
preOrder(ptr->lchild);
preOrder(ptr->rchild);
}
}
//中序遍历
void inOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
inOrder(ptr->lchild);
printf("%c ",ptr->data);
inOrder(ptr->rchild);
}
}
//后序遍历
void postOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
postOrder(ptr->lchild);
postOrder(ptr->rchild);
printf("%c ",ptr->data);
}
}
int main()
{
Bitree *root;
printf("创建二叉树,输入前序扩展序列: ");
CreateBiTree(&root);
printf("前序遍历序列: ");
preOrder(root);
printf("\n中序遍历序列: ");
inOrder(root);
printf("\n后序遍历序列: ");
postOrder(root);
printf("\n");
return 0;
}
追问前序CFIJ，中序CIFJ，
不是说对于右子树也要用相同的序列方式操作吗？
遍历第一个右边的时候，
前序是根，左，右
中序是左右根
怎么确定C就是下一个结点啊？
我在这里搞不懂，左边的都读的来
不知道哪里出问题了
求求大神叫叫鄙人
教教