完全二叉树的性质和顺序存储结构 (1)具有n个结点的完全二叉树的高度=log2(n+1) (2)若将一棵按前述原则编号的完全二叉树,按其编号顺序存入 个一维数组中,则有 结点i的左子结点下标=2*i+1<n 结点i的右子结点下标=2*i+2<n 结点i的父结点下标=(i-1)/2的下取整值 另外注意:根结点(下标为0)无父结点 由上可知,完全二叉树的父—左子、父—右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来,因此可以采用顺序存储结构来存储完全二叉树。(参见 教材6.3.1数组表示 顺序存储结构用于动态性较小的完全二叉树的存储不失为 种简单有效的方法,但不通用。树型数据结构一般采用链式存 储方式来存储。 20212222021/2/22 5 完全二叉树的性质和顺序存储结构 （1）具有n 个结点的完全二叉树的高度= log2 ( n + 1 ) – 1 （2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一 个一维数组中，则有： 结点 i 的左子结点下标= 2* i + 1 < n 结点 i 的右子结点下标= 2* i + 2 < n 结点 i 的父结点下标= ( i – 1 ) / 2 的下取整值 另外注意：根结点（下标为0）无父结点 由上可知，完全二叉树的父——左子、父——右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来，因此可以采用顺序存储结构来存储完全二叉树。（参见 教材 6.3.1 数组表示） 顺序存储结构用于动态性较小的完全二叉树的存储不失为 一种简单有效的方法，但不通用。树型数据结构一般采用链式存 储方式来存储