二叉树

文章目录

1. 1. 概念
2. 2. 性质
3. 3. 分类
   1. 3.1. 满二叉树
   2. 3.2. 完全二叉树

概念

二叉树（Binary tree）是有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做“左子树”，另一棵叫做根的“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

性质

1. 在二叉树中第 i 层的结点数最多为 2^(i-1)（i ≥ 1）
2. 高度为 k 的二叉树其结点总数最多为 2^k－1（ k ≥ 1）
3. 对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1

   分类

   满二叉树

   如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
   

满二叉树除了满足普通二叉树的性质，还具有以下性质：

1. 满二叉树中第 i 层的节点数为 2^(n-1) 个。
2. 深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^(k-1)。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。(符号为向下取整)

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如上图 a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。