已知二叉树的前序序列为bcdefag,中序序列为dcfaegb,请问后序序列为
后序序列为DCBA。
详解为:前序序列的顺序是根、左、右,序列ABCD第一个一定是根结点,A是根节点。中序序列顺序是左、根、右,因为A是根节点,所以DCB位于A左侧,A右侧没有结点,B是DCB三个结点中的根。前序序列是中左右,根结点为A;中序序列是左中右,左子树BCD;遵循遍历序列的规则排列出二叉树,得出后序遍历为DCBA。
拓展资料在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。
一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。
二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。
有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。
已知 前序序列为bcdefag 中序序列为dcfaegb 得知 后序序列为dafgecb
分析过程:
根据 前序序列bcdefag, 得知b是根结点.
那么,中序序列dcfaegb里,以b为中心,划分左子树和右子树, 得到(dcfaeg)(b)
得知根结点b只有左子树dcfaeg:
b
/
dcfaeg
前序序列bcdefag, 其中c在b的后面, 而d在c的后面, 预计c是b的左子树
中序序列dcfaegb, 其中d排在首位,而c在d的后面, 可知d是最左边的结点,
d没有左子树, d是c的左子树:
b
/
c
/
d
前序序列bcdefag, 其中e在d的后面, 而e后面是fa
中序序列dcfaegb, 其中e排在fa之后, 预计e是c的右子树,fa是e的左子树:
b
/
c
/ \
d e
/
fa
前序序列bcdefag, 其中f在a的前面.
中序序列dcfaegb, 其中f在a的前面, 可知f没有左子树, f的右子树是a:
b
/
c
/ \
d e
/
f
\
a
前序序列bcdefag, 其中g排在最后.
中序序列dcfaegb, 其中g在(dcfaeg)里排在最后, 得知g是e的右子树:
b
/
c
/ \
d e
/ \
f g
\
a
上图就是二叉树的示意图.
所以,后序序列为 d a f g e c b
C语言测试程序
测试结果:
创建二叉树,输入前序扩展序列: bcd##ef#a##g###
前序遍历序列: b c d e f a g
中序遍历序列: d c f a e g b
后序遍历序列: d a f g e c b
#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("
中序遍历序列: ");
inOrder(root);
printf("
后序遍历序列: ");
postOrder(root);
printf("
");
return 0;
}
已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEI...
根据先序遍历和中序遍历,我们可以将这颗二叉树画出来,如下图。所以,根据图片,得出层次遍历序列为:ABCDEFGHI。
已知二叉树的前序遍历和中序遍历,怎样得到它的后序
已知二叉树的前序遍历和中序遍历 步骤一:从前序遍历序列中找到根结点(首结点)步骤二:然后从中序序列中找到该节点的左右两个中序序列,取出该结点放置到两序列之后。步骤三:针对划分后的两个中序序列重复步骤一和步骤二,直到中序序列无法再次划分。此时得到的序列即为后序序列。(方法二)
已知某二叉树的前序序列为eb
前序是根,左孩子,右孩子.中序是左孩子,根,右孩子 现在前序是:ABCDE,中序是CBDAE,所以A是根节点,CBD是左孩子,E是右孩子 再根据先序BCD,中序CBD得知,B是左孩子CBD的根,C是左孩子,D是右孩子.结束 图如下: A \/ \\ B E \/ \\ C D ...
二叉树已知某二叉树的先序序列和中序序列分别?
ABC,如果是先序,A是根,B是左叶,C是右叶;ABC如果是中序,A是左叶,B是根,C是右叶。先序序列ABDEFCGHIJK,说明A是这个树的总根;中序EFDBCGAJIKH,说明E是最底层最左边的叶子,(EFDBCG)是左枝,(JIKH)是右枝。据此,我们可以把这个二叉树,第一次分层为:先序A(BDEFCG)(HIJK)中序(EFD...
二叉树前序中序后序
二叉树前序中序后序如下:①前序遍历的方式是:首先访问根节点,然后访问左子树,最后访问右子树。前序遍历序列:F C A D B E H G M。②中序遍历的方式是:首先访问左子树,接着访问根结点,最后访问右子树。中序遍历序列:A C B D F H E M G。③后序遍历的方式是:首先访问左子树,接...
已知某二叉树的前序是abdgcefh,中序dgbaechf,则后序是?
首先我们知道,前序遍历的规则是:根结点→左子结点→右子结点 中序遍历是:左子结点→根结点→右子结点 后序遍历是:左子结点→右子结点→根结点 那么,对于一棵二叉树,前序遍历的第一个结点一定是这棵树的根结点,即根结点是a。在中序遍历的顺序dgbaechf中,以a分成左、右两边,左边是dgb,...
如何根据二叉树的前序遍历和中序遍历如何构建二叉树
已知一棵二叉树的前序序列和中序序列,构造该二叉树的过程如下:1. 根据前序序列的第一个元素建立根结点;2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;3. 在前序序列中确定左右子树的前序序列;4. 由左子树的前序序列和中序序列建立左子树;5. 由右子树的前序序列和中序序列...
如何确定二叉树的先序,中序和后序呢?
二叉树的先序,中序,后序确定的方法如下:1、根据后序遍历的特点,我们知道后序遍历最后一个结点即为根结点,即根结点为G。2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树,G右侧的HMZ必然是root的右子树。3、观察左子树ADEF,左子树的中的根节点必然是大树的root的left...
已知二叉树的前序遍历序列为abdehcfg,中序遍历序列为dbheafcg,画出二叉...
前序中的第一个为根,在中序中找到根,左边的为左子树,右边的为右子树。然后递归这个过程 后续遍历为dhebfgca
已知二叉树的前序和中序后序 怎么用c求它的层次遍历
无需建立二叉树:获取当前前序序列的第一个元素并输出(按层次遍历)从对应的中序序列中找到该元素,该元素此时将二分中序序列中的元素 依据划分出的两个序列,在前序序列中找到这两个序列(按照中序中序列的元素个数即可划分)对划分后的先序序列继续1,2,3两步(要平行进行不能处理完一个序列再...
游永脑得: 设某二叉树的前序序列为ABC,中序序列为CBA,则该二叉树的后序序列为 CBA .
白城市19526578971: 数据结构 已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ,中序遍历的结果是 - ?
游永脑得: 如果仅有“已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ”,则中序遍历的结果是不能确定的.
白城市19526578971: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么? - ?
游永脑得: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点.中序遍历的根节点前面的节点均为左子树的节点,所以左子树上...
白城市19526578971: 已知一棵二叉树的前序序列和中序序列分别是ABCDEFGHIJ和BAEDCHGIFJ,构造二叉树,并写出其后序序列 - ?
游永脑得:[答案] 这是递归算法. 前序第一个必定是根,根就是A, 从中序中就能分出左、右子树了:B和EDCHGIFJ,这是中序 就可据此从前序中分出左、右子树了:B和CDEFGHIJ,这是前序了. 这样一个问题变成了两个同样的小问题了,递归下去不就解决了. 多动...
白城市19526578971: 已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历序列为CBDEAFHIGJ. - ?
游永脑得: 1 答案不唯一 2 e位置错误
白城市19526578971: 已知二叉树序列已知二叉树的前序序列为ABCDEFGHIJ,中序序列为 DBGEAHFIJC,写出后序序列? - ?
游永脑得:[答案] 序列不对,前序序列A是开头,说明A是根节点,在中序序列中,A的左边是左子树,右边是右子树.而C在前序中是左子树.在中序中居然跑到右子树去了.序列有问题
白城市19526578971: 1. 已知一棵二叉树的中序遍历序列为CDBAEGF,前序遍历序列为ABCDEFG,问能否唯一确定一棵树,请画出.若给 - ?
游永脑得: 图形不好画 A的左子树是C右子树是E C的左子树是B右子树是D E的右子树是F F的左子树是G前序为ACBDEFG
白城市19526578971: 已知二叉树的前序和中序,构造该二叉树的方法是什么 - ?
游永脑得: 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根...
白城市19526578971: 一道二叉树题目已知某二叉树的前序序列是ABCD,中序序列是DBAC,问后序序列是_____.求给图,怎么想都想不出,郁闷了. - ?
游永脑得:[答案] 如果前序序列是ABCD,中序序列是DBAC,则没有二叉树这样的,原因:从前序得出A为根,回到中序切分为左子树DB、根A、右子树C接下来回到前序,A遍历完了就是左子树的,然后右子树的,产生矛盾了,所以无答案不过将前序改为层次序,...
白城市19526578971: C++: 某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树的先序序列为( - ?
游永脑得: 已知某二叉树的中根遍历序列是ABCDEFG,后根遍历序列是BDCAFGE,则它的先跟遍历序列是:EACBDGF. 首先明确先跟遍历:中左右;中根遍历:左中右;后根遍历:左右中. 1、后根遍历明确根节点是E,中根遍历确定左子树是...