试题题干
高度为3、含有5个结点(编号1～5)的二叉树，其顺序存储结构为
，则编号为4的结点的双亲结点的编号为
。
参考答案
试题解析
本题考查二叉树的顺序存储和二叉树的性质5。
顺序存储的非完全二叉树（即本题的二叉树），首先必须用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。 即无结点的位置编号为0。
性质5：如果将一棵有n个结点的完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有n个结点按从第一层到最大层，每层从左到右的顺序依次标记为1, 2,…， n。则对任一编号为i（1≤i≤n）的结点A有：
（1）若i=1，则结点A是根；若i>1，则A的双亲Parent(A)的编号为⌊i/2⌋；
（2）若2*i>n，则结点A既无左孩子，也无右孩子；否则A的左孩子Lchild(X)的编号为2*i;
（3）若2*i+1>n，则结点A无右孩子；否则，A的右孩子Rchild(X)的编号为2*i + 1。
编号为4的存储位置是6，故其双亲的存储位置是⌊6/2⌋=3，编号为3。