Question

求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。

Answer 1

根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是en/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的，叶子结点的下标是en/2u+1。

最坏的情况就是这个二叉树是单支数。 比如有k 层，节点数字也是 k 。需要 2^K - 1 长度dao的数组来存放，而实际上它只有 k 个节点。因为二叉树的顺序存储是相对完全二叉树而言的。

对于一般的二叉树，如果相对于二叉树没有这个节点，也要在数组中的对应位置存放一个标识，表示没有该节点。

扩展资料：

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。

采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

参考资料来源：百度百科-顺序存储结构

Answer 2

根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是en

/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的

叶子结点的下标是en/2u+1