问答题 如果一棵有n个结点的满二叉树的高度为h(根结点所在的层次为1),则求解下列问题。 (1)用高度如何表示结点总数n?用结点总数n如何表示高度h? (2)若对该树的结点从0开始按中序遍历次序进行编号,则如何用高度h表示根结点的编号?如何用高度h表示根结点的左子女结点的编号和右子女结点的编号?
【正确答案】按照题意,该满二叉树的高度为h,结点总数为n,则:
(1)按照满二叉树的性质,n=2h-1;反之,h=log2(n+1)。
(2)用高度h确定根结点编号的依据有以下3种。
1)从满二叉树推知,结点数有n=2h-1个,编号从0到n-1,即0~(2h-2)。
2)由于是按中序遍历次序所作的编号,根结点的左、右子树的结点数相等,根结点的编号应位于正中。
3)按照求中点的公式,中点的编号应为mid=(low+high)/2=(0+2h-2)/2=2h-1-1,此即满二叉树根结点的编号。依次类推,根结点左子树有2h-1-1个结点,其结点编号从0到2h-1-2,左子树根结点(即根结点左子女结点)的编号为2h-2-1;而右子女结点的编号为2h-1+(2h-2-1)=3×2h-2-1。
【答案解析】