Question

树、二叉树分类以及内部节点的关系

Answer 1

按照分类可以分为以下几种：

二叉树是树中常用的结构，它有着如下的几个特性（假定 层数i是从1 开始）:

二叉树又分为以下几种类型:

注意：

注意：
假如 完全二叉树 的高度为 h（h >= 1） ，总结点个数 n 个，那么有着以下重要特性：

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

如果一棵完全二叉树有768个节点，那么叶子节点的个数是多少？
假设叶子度为 0 的节点个数为 n0 ，度为 1 的节点个数为 n1 ，度为 2 的节点个数为 n2 ，那么总结点个数有这如下关系：

由于完全二叉树度为 1 的数量要么是 0 ，要么是 1 ，所以这里分为两种情况：

大致也能得出结论，总节点如果是奇数，那么叶子节点 n0 = (n + 1) / 2 ，为偶数的时候，叶子节点个数为 n0 = n / 2

在计算的时候可以简化两种情况，因为最终获取的内容为整数，所以如果 统一两种行为 ，可以选择 统一使用奇数情况 计算，也即 n0 = (n + 1) / 2 。这个计算方法在节点数为奇数的情况下是没有问题的，但是如果是偶数的情况下，结果会出现小数，多出的小数实际上在偶数情况下是不需要的，为了容错，所以此时可以采取向下取整的方式 将小数舍弃 ，进而进行 偶数的容错 ，从而达到 两种情况兼容 的目的。

所以最终的方法可以通用以下的方式来算出度为0的节点个数：
floor((n + 1) >> 1)