二叉树的排序1.一个具有767个结点的完全二叉树,其叶子节点数<>A.383B.384C.385D.3862.深度为5的满二叉树,叶子结点的个数为3.一棵二叉树前序排列和中序排列分别是：abdegcfh和dbgeachf后序排

Question

二叉树的排序
1.一个具有767个结点的完全二叉树,其叶子节点数< >
A.383 B.384
C.385 D.386
2.深度为5的满二叉树,叶子结点的个数为______
3.一棵二叉树前序排列和中序排列分别是：abdegcfh和dbgeachf
后序排列为_______________________

Answer 1

1.答案：C
分析：根据性质“深度为K的二叉树至多有2k -1个结点（k≥1）”可知,具有结点767是深度为10完全二叉树.前9层的结点有29-1=511个结点,在第10层的结点个数就为767-511=256,那么在第9层中具有两个子结点的结点数为256/2=128,则整个二叉树具有两个子结点的结点数为28 -1+128=384,又根据性质“对任何一棵二叉树,如果其叶子节点数为n0,具有两个子结点的结点数为n2,则 n0=n2+1”,叶子节点数为384+1=385.
2.答案：16
分析：根据性质“在二叉树的第i层上至多有2i-1个结点”,深度为5的满二叉树的叶子结点数即为 第5层的结点数25-1=16.
3.答案：dgebhfca
分析：排列的概念问题,就不多说了.从前序排列可以得出,树的根节点为a,根节点的左节点为b,再根据中序排列中从根节点a的左右分开分别为左右子树的结点,左子树为dbge,右子树为chf,再根据前序排列c为右子树第一个即为根节点的右结点.再根据中序排列中右边根节点的左边为d,即d为b的左子树且可以看出d没有左右子树,又在根据前序排列中e紧跟在b后面得出e为b右子树,再根据根据中序排列中g在e前得出g为e的左子树.
根节点的右子树就不多做分析了,原理类似.最后得出如下二叉树,最后再进行后序排列.