完全二叉树 满二叉树: 完全二叉树: 1、满二叉树 每层结点 2、从满二叉树 数最多 最底层从右向左 依次去掉若干结 点形成的 P)(a)(R)(s)(u)(v)(w 性质4:具有n个结点的完全二叉树高度为ogn」+1 证:根据性质2和完全二叉树的定义:设其高度为k 2k-1-1<n<=2k-1 k-1<n+1<=2k 2k1<=n<2 故:k-1<=log2n<k;原命题得证。完全二叉树 B C E F D L A P Q R S U B C E F D L A P Q R S U V W X •满二叉树: 每层结点 数最多 •完全二叉树: 1、满二叉树 2、从满二叉树 最底层从右向左 依次去掉若干结 点形成的 性质4：具有 n 个结点的完全二叉树高度为 log2n + 1 证：根据性质 2 和完全二叉树的定义：设其高度为 k 2 k-1 -1< n <= 2k -1 2 k-1 < n + 1 <= 2k 2 k-1 <= n < 2k 故：k-1 <= log2n < k ; 原命题得证