> 文章列表 > 关于二叉树访问顺序的选择题

关于二叉树访问顺序的选择题

关于二叉树访问顺序的选择题

 第一题:

 从题目中我们可以得出这是棵完全二叉树(最后一列不满,且连续),层次顺序。

我们可以推出树的形状:

我们现根据层次遍历的性质画出出栈的图:

ABCDEFGH 

 最开始是A所以第一个位置为A,A出来后带进来BC,B出来后带进来DE,C出去后带进来FG,D出去后带进来H

因为这棵树为完全二叉树,最后一层不满且为连续的,所以H只能放在D的下面。

形状:

我们再由次推出先序(根左右)的排列 :ABDHECFG

 第二题:

 题目告诉了我们先序和中序,让我们推出它的根,其实这题很简单答案直接为E,因为先序起始节点就是根节点。但我们要求画出树的形状不能只局限于求其根,还要解其树。

解释:由先序我们确定根,再看待中序(左中右)推出E左边的全在左节点,右边的全在右节点

确定E的left和right

由前序EF推出E left为 F,因为E的左边包含了HFI,且前序为根左右,所以E的right为HFI后面的第一个子节 G

确定F的left和right

由中序我们可以看出F left为H right为I

确定G的left和right

因为确定G为根所以先序中G后面为J所以G的left为J,由中序中K在G前面推出K不可能为G的右节点(左根右),又因为前序和中序中K在J后面所以突出K不可能为J的左节点只能为J的右节点

第三题:

 

 

 由中序和后序dce都连着我们可以推出c为de的根,且d为left,e为righ

又因为中序中的ba突出b为a的left,因为后序中c后面为a所以c为a的right。