二叉树基础

简介：
《二叉树基础》是一本介绍数据结构中重要组成部分——二叉树的基本概念、类型及其操作方法的书籍。适合编程初学者阅读。 在计算机科学领域内，二叉树是一种特殊的树结构，每个节点最多拥有两个子节点，并且这两个子节点被明确区分为主“左子树”与“右子树”。这种数据结构常用于构建诸如二叉查找树或二叉堆等应用。 具体而言，在一棵典型的二叉树中，每一层的结点数不会超过2^(i-1)，其中 i 表示该层次的位置。对于深度为 k 的二叉树来说，其最大节点数量则不超过 2^k - 1 。另外还存在一个有趣的关系：如果某棵二叉树拥有 n_0 个终端（叶子）结点和 n_2 个度数为2的非叶结点，则有 n_0 = n_2 + 1 成立。 基于上述定义，当一棵深度为 k 的二叉树恰好包含满额数量(即 2^k - 1 )的节点时，我们称它为“完全”的。这类结构的一个显著特征在于除了最后一层外的所有层级都达到了最大容量；并且在最底层中要么全部填满了结点，要么仅从右侧开始有连续缺失的情况。 对于具有 n 个节点的完全二叉树而言，它的深度可以表示为 log2(n) + 1 。同样地，在一个高度固定为 k 的完全二叉树里，其包含的最少和最多的节点数量分别为 2^(k-1) 和 (2^k - 1)。