完全二叉树中有多少个叶子结点?

Question

如题所述

Answer 1

设一棵完全二叉树共有500个结点，则在该二叉树中有250个叶子结点。

满2叉树的结点是2的K次方减1。所以，满2叉树应该有511个结点、但现在只有500个。所以缺少了11个右结点。是最后一层上少了倒着少了11个结点。明确的说是少了6个右，5个左。

所以，应该256-11，但是由于最后一层少了11个结点，所以上一层多了5个叶子结点，所以最终答案应该是：256-11+5=250。

扩展资料

类型：

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。