二叉树的中序遍历为:4、5、2、1、6、3、8、7、9.后序遍历为:5、4、2、6、8、9、7、3、1,画出二叉树
由前序遍历得知 1 为根结点,则由中序遍历可知, 4 、2为其左子树, 5 、7、3、6 为右子树, 则在根据前序遍历4 、2 顺序得知 2 为根,从中序得知 4 为 2 的左子树, 以此类推,可得到一个二叉树, 其后序遍历则为
4 2 7 5 6 3 1
答案:A:5 , 3 , 6 , 4 , 2 , 9 , 10 , 8 , 7 , 1,B:6 , 3 , 5 , 2 , 4 , 10 , 9 , 7 , 8 , 1,C:6 , 3 , 5 , 4 , 2 。
9 , 10 , 8 , 7 , 1,D:6 , 3 , 4 , 5 , 9 , 2 , 10 , 7 , 8 , 1,6 , 3 , 5 , 4 , 2 , 9 , 10 , 8。
前序遍历(VLR),[1]是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。
简介
前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
若二叉树为空则结束返回,否则:
(1)访问根结点。
(2)前序遍历左子树。
(3)前序遍历右子树 。
需要注意的是:遍历左右子树时仍然采用前序遍历方法。
如图1所示二叉树
前序遍历结果:ABDECF
已知后序遍历和中序遍历,就能确定前序遍历。
前序遍历:访问根结点的操作发生在遍历其左右子树之前。
中序遍历:访问根结点的操作发生在遍历其左右子树之中(间)。
后序遍历:访问根结点的操作发生在遍历其左右子树之后。
来看你的题目:
1.由后序遍历5、4、2、6、8、9、7、3、1可知根为1
2.在中序遍历4、5、2、1、6、3、8、7、9中找到1,可知(左)452-1-63879(右)
对左右支分别重复上述步骤,即
在后序遍历中观察452的相对位置可知2为根,则有45-2-空
在后序遍历中观察63879的相对位置可知3为根,则有6-3-879
……
由此可得出树的结构为
------------------------------1
---------2L 3R
----4L 空 6L 7R
-空 5R 空 空 8L 9R
图中L表示左,R表示右,用空格区分位置,希望楼主能够明白
步骤:
后序最后一个值为1,则表示根节点为1。
查看中序由1,分割成 452 和 63879 两棵子树。
对“左子树”---中序452和后序542,得到根节点为2。中序452表明45组成2的左子树,根节点为4,5为4的右子树。
对“右子树”---中序63879和后序68973,得到根节点为3。6为左子树,右子树为--中序879和后序897。所以根节点为7,左子树为8,右子树为9。
所以最后是 1
/ \
2 3
/ / \
4 6 7
\ / \
5 8 9
/*
10 用0替代 运行C程序 输入如下:
***********Bitree*****
input a tree preorder:
1236457890
input a tree midoeder:
3625419807
1236457890
3625419807
6354290871
结果为:6 3 5 4 2 9 10 8 7 1
*/
#include <stdio.h>
#include <stdlib.h>
#define max 100
typedef char ch[10];
void fun(ch x,ch y){
if(*x){
ch x1,x2,y1,y2;
char *p,*q,*t; char r; int n=0;
r=*x; t=y; p=y1; q=y2;
while(*t!=r){
*(p++)=*(t++);
n++;
}
t++; *p='\0';
while(*t) *(q++)=*(t++);
*q='\0'; t=&x[1]; p=x1; q=x2;
for (int i=0;i<n;i++) *(p++)=*(t++); *p='\0';
while(*t) *(q++)=*(t++); *q='\0';
fun(x1,y1); fun(x2,y2);
printf("%c",r);
}
}
void f(){
ch x,y;
printf("input a tree preorder:\n"); gets(x);
printf("input a tree midoeder:\n"); gets(y);
printf("\n");
puts(x); puts(y);
fun(x,y);
printf("\n");
}
void main(){
printf("***********Bitree************\n");
int n=1;
while(n){
f();
printf("0:break 1 :continue\n");
printf("input your select :");
scanf("%d",&n); getchar();
}
}
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前...
后序遍历顺序是“左子树―右子树―树根节点”:中序遍历是“左子树-树根节点-右子树”,前序遍历是“树根节点―左子树―右子树”。二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。四种遍历方式分别为:先序...
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉...
由前序遍历,C是二叉树的右根节点,由中序遍历,C不含左子节点,HF为C的右子节点。由前序遍历,F为H的根节点,由中序遍历,H为F的左子节点。在二叉树中,求后序遍历,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。
计算机二级二叉树前序中序后序
下图中1为主根结点,245为左子树,367为右子树;在左子树中,2为根结点,4为左子树,5为右子树;在右子树中,3为根结点,6为左子树,7为右子树。依次将每个树中的根结点、左子树以及右子树分清,只到子树中只剩一个元素为止。综上可知,结果为1→2→4→5→3→6→7。例子 2、 中序遍历 ...
构造一棵二叉树,并分别输出其先序遍历、中序遍历和后序遍历的结果
cout<<"请输入相应二叉树:"<<endl;CreateBiTree(T);cout<<"二叉树的先序遍历为:"<<endl;preBiTree(T);cout<<endl;cout<<"二叉树的中序遍历为:"<<endl;InBiTree(T);cout<<endl;cout<<"二叉树的后序遍历为:"<<endl;PostBiTree(T);cout<<endl;cout<<"二叉树的深度为:"<<endl;cou...
什么情况下二叉树的中序和后序序列相同
分析如下:二叉树的中序序列为:左子树、根、右子树;二叉树的后序序列为:左子树、右子树、根;要想使二叉树的中序和后序序列相同,则只有两种情况可以满足:1、没有根的二叉树,然而根据二叉树的性质可知,所有的二叉树都有有根节点的,因此此项不满足;2、没有右子树的二叉树,只有左子树的...
中序遍历二叉排序树可以得到一个有序的序列,是否正确?
【正确】二叉排序树的左子树一定小于根节点,右子树一定大于根节点,中序遍历的顺序是首先中序遍历左子树,然后访问根节点,最后中序遍历右子树,所以中序遍历二叉排序树可以得到一个有序序列。
二叉树的先根,中根,后根怎么算?
这里的“先根”也叫做先序,“中”和“后”也一样。先序遍历是先访问当前节点,然后再遍历左子树,最后是右子树。中序遍历是先遍历左子树,再访问当前节点,最后是右子树。后序遍历是先遍历左子树,再遍历右子树,最后访问当前节点。树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中...
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。这句话对吗...
因为二叉排序树的根节点大于左子树,小于右子树,然后使用中序遍历算法,中序遍历算法先遍历左子树,然后是根节点,然后是右子树。根据遍历的特性,所有的先遍历的结点,一定是小于后边遍历的结点,所以说中序遍历一棵二叉排序树的结点就可以得到一个排好序的序列。
如果一棵二叉树的中序序列和后序序列分别为CDBEAGHFK和DCEBHGKFA,则该...
再从中序序列CDBEAGHFK可以知道,CDBE是根A的左子树中的结点,而GHFK是根A的右子树中的结点。现在我们来分析左子树中的情况,同样由后序序列中DCEB可以看出B是左子树的根结点,由中序序列CDBE可以看出E是B的右子树的结点。同理,我们可以分析出整个二叉树的结点分布。此二叉树前序遍历的结果为...
某二叉树,先序ABDGCEFH,中序DGBAECHF,求后续遍历的解题思路有哪些...
分析过程:以下面的例题为例进行讲解:已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列。分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序...
咎育重酒: 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个节点仅被访问一次的过程. 1、先序遍历(前序) (1)访问根节点; (2)先序遍历左子树; (3)先序遍历右子树. 2、中序遍历 (1)中序遍历左子树; (2)访问根节点; (3...
衡东县19258444702: 二叉树遍历问题(前序,中序,后序) - ?
咎育重酒: 前序遍历(DLR) 前序遍历也叫做先根遍历,可记做根左右. 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树.在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树. 若二叉树为空则结束返回,否则: ...
衡东县19258444702: 输入中序遍历和后序遍历怎么构造二叉树 - ?
咎育重酒: 这里的“先根”也叫做先序,“中”和“后”也一样.先序遍历是先访问当前节点,然后再遍历左子树,最后是右子树.中序遍历是先遍历左子树,再访问当前节点,最后是右子树.后序遍历是先遍历左子树,再遍历右子树,最后访问当前节点...
衡东县19258444702: 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1.则该二叉树的中序遍历序列不会是a.1234 b.2341 c.3241 d.4321单选,2011计算机考研... - ?
咎育重酒:[答案] 答案的确是c,你说的1为根结点也没有错,因为根据前序和后序的结论都说明如此,不过那个说明3是根错了 按照条件就可以知道结点1在第一层,2在第二层,3在第三层,4在第四层,因此中序遍历abd都有可能出现,但是对于答案c而言,如果第...
衡东县19258444702: c语言,计算机基础,请问已知二叉树的中序遍历为BDCEAFHG,和后序遍历EDCBHGFA,二叉树 - ?
咎育重酒: 中序遍历为BDCEAFHG(左根右) 后序遍历EDCBHGFA(左右根) 所以,根为A,左子树BDCE,右子树FHG 同理,再次可求得左子树BDCE中B应为左子树:但在后序遍历中B为EDCB中的根. 所以,题目有错. 如有疑问,请追问.
衡东县19258444702: 二叉树的前、中、后三种遍历的解答方法? - ?
咎育重酒: 二叉树的遍历: (1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树; (2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树; (3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点.
衡东县19258444702: 二叉树中的中序遍历和先序遍历是什么意思? - ?
咎育重酒: 这里的序是指访问父节点,其余按先左儿子,后右儿子 中序遍历就是中间访问父节点,就是左儿子、父节点、右儿子 先序便利就是父节点、左儿子、右儿子 后序遍历就是左儿子、右儿子、父节点 看你这个图,先看根节点,中序遍历先遍历左子...
衡东县19258444702: 何谓二叉树的遍历? - ?
咎育重酒: 就是按照一定的顺序访问二叉树中的每一个节点.顺序一般有先序遍历,中序遍历和后序遍历 1.中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1)遍历左子树; (2)访问根结点; (3)遍历右子树.2.先序遍历的递归算...
衡东县19258444702: 计算机,数据结构,二叉树的遍历,先序遍历,后序遍历,中序遍历,急急急急急急,跪求高手帮助 - ?
咎育重酒: 中序遍历为ABCD,前序遍历序列为CABD 前序遍历先访问根,所以C为根,在中序遍历中先访问左子树,再访问根,最后访问右子树,所以在中序序列中,C前面的为左子树,第二个访问的是左子树的根A以此类推可得这样的一棵二叉树: C / \ A D \ B 对这棵二叉树后序遍历可得后序序列为BADC
衡东县19258444702: 什么是先、中、后根遍历?什么是左子树、右子树和二叉树? - ?
咎育重酒: 1、先根遍历一般是先序遍历(Pre-order),按照根左右的顺序沿一定路径经过路径上所有的结点.在二叉树中,先根后左再右.巧记:根左右. 首先访问根结点然后遍历左子树,最后遍历右子树.在遍历左、右子树时,仍然先访问根结点,然...