二叉树 #

1. 二叉树的定义
2. 二叉树的一些性质
3. 满二叉树和完全二叉树

二叉树的定义 #

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树。

• 二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树
• 二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树的一些性质 #

• 二叉树中，第 i 层最多有 2^i-1个结点
• 如果二叉树的深度为 K，那么此二叉树最多有 2^k-1 个结点
• 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1

满二叉树和完全二叉树 #

二叉树还可以继续分类，衍生出满二叉树和完全二叉树

• 如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树
• 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树

小结 #

1. 理解二叉树的定义
2. 了解二叉树的性质
3. 理解完全二叉树以及满二叉树的概念

习题 #

• 对于一颗深度为n的满二叉树，它的节点个数是多少？它的叶节点个数是多少？它的双亲节点个数是多少？
• 一颗完全二叉树的节点个数为n，那么它的深度是多少？它的叶节点个数是多少？尝试举例说明