数据结构考研分类复习真题 第六章 答案 (四)[6]

用顺序存储结构存储n个结点的完全二叉树编号为i的结点其双亲编号是ëi/û(i=时无双亲)其左子女是i(若i<=n否则i无左子女)右子女是i+(若i+<=n否则无右子女)

根据完全二叉树的性质最后一个结点（编号为n）的双亲结点的编号是ën/û这是最后一个分枝结点在它之后是第一个终端（叶子）结点故序号最小的叶子结点的下标是ën/û+

按前序遍历对顶点编号即根结点从１开始对前序遍历序列的结点从小到大编号

设树的结点数为n分枝数为B则下面二式成立

n=n+n+n+…+nm ()

n=B+= n+n+…+mnm ()

由()和()得叶子结点数n=+

élognù +

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []