数据结构二叉树

二叉树的基本概念

定义：二叉树（binary tree）是一棵 度为二 的树，其孩子有左右之分，也分别都是二叉树。(度绝对不可以超过 2，且是一个有序树)

二叉树的重要性质

性质一: 在二叉树的第 i 层上最多有 2^(i-1)个结点（i≥1）。

性质二: 深度为 k 的二叉树最多有 2^k- 1 个结点（k≥1）。

性质三: 对任一二叉树，叶子结点数为 X，度为 2 的结点数为 Y，则 X =Y+1。

衍生出两类二叉树

1. 满二叉树（full binary tree）：一棵深度为 k 且有 2^k- 1 个结点的二叉树称为满二叉树。
2. 完全二叉树（complete binary tree）：一棵深度为 k 的满二叉树的第 k 层的右边几个结点不存在则为完全二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质:

性质四:n 个结点的完全二叉树的深度为 ⌊log2 n⌋+1。

性质五: 对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i，完全二叉树还有以下 3 个结论成立：

• 当 i>1 时，父亲结点为结点 [i/2]。（i=1 时，表示的是根结点，无父亲结点）
• 如果 2×i>n（总结点的个数），则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2×i。
• 如果 2×i+1>n，则结点 i 肯定没有右孩子；否则右孩子是结点 2×i+1