Question

数据结构 - 二叉树

Answer 1

一棵树可以没有任何节点称为 空树 ，可以只有一个节点root
一棵树可以分为多个子树组合，二叉树有左子树、右子树。
节点的度： 这个节点子树的个数。上图的节点1度为5，节点2的度为2。
树的度： 所有节点度中的最大值，上图的树的度为5
叶子节点： 度为0的节点
层数： 根节点在第一层，根节点的子节点在第二层。以此类推
节点的深度： 从根节点到当前节点的唯一路径上的节点总数，如图22的深度为3
节点的高度： 从当前节点到最远叶子节点的路径上的节点总数，如图22的高度为2
树的深度： 所有节点深度中的最大值，图中树的深度为4
树的高度： 所有节点高度中的最大值，图中树的高度为4

特点：

以下都是二叉树

二叉树的特性：

所有的节点度要不为0 要不为2

最后一层节点的度都为0，其他节点的度为2

假设满二叉树的高度为 h（h >= 1） ，那么

对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应

下图不是完全二叉树

完全二叉树的性质

假设完全二叉树的高度为 h（h >= 1） ， 那么

一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点

一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 0 开始进行编号，对任意第 i 个节点

面试题：
如果一棵完全二叉树有 768 个节点，求叶子节点的个数？

解题：384
假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2
总结点个数 n = n0 + n1 + n2，而且 n0 = n2 + 1
所以： n = 2n0 + n1 – 1

完全二叉树的 n1 要么为 0，要么为 1
n1为1时，n = 2n0，n 必然是偶数
叶子节点个数 n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2
n1为0时，n = 2n0 – 1，n 必然是奇数
叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n – 1) / 2

叶子节点个数 n0 = floor( (n + 1) / 2 )= ceiling( n / 2 )
非叶子节点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )