数据结构重学日记（十六）二叉树的概念

概念

是每个结点最多有两个子树的树结构。左右子树顺序不能颠倒，统常子树被称为左子树和右子树。

5 种基本形态

• 空树
• 只有一个根结点
• 根结点只有一个左子树
• 根结点只有一个右子树
• 根结点既有左子树也有右子树

斜树

所有结点只有左子树或右子树，每层只有一个结点，结点树与树的深度相同

斜树

满二叉树

所有结点都存在左子树和右子树，并且所有的叶子都在同一层。

满二叉树

特点

• 叶子只存在于最底层
• 非叶子结点度一定是 2
• 在同样深度的二叉树中，满二叉树的结点数最多，叶子最多。

完全二叉树

对一棵具有 n 个结点的二叉树按层序拍好，若果编号为 i 的结点与同样深度的满二叉树编号为 i 的结点在二叉树中的位置完全相同，就是完全二叉树，满二叉树必须是完全二叉树，反过来不一定成立。

特点

• 叶子只能在最下层
• 如果有度为 1 的结点，有且只能有一个，且该结点只有左子树无右子树
• 同样结点数的二叉树中，完全二叉树的深度是最小的。

完全二叉树

二叉树的性质

• 非空二叉树上叶子结点树等于度为 2 的结点数 + 1
• 非空二叉树上第 k 层最多有 个结点（k >= 1）
• 高度为 h 的二叉树最多有 - 1个结点（h >= 1）
• 具有 n 个结点的完全二叉树的高度为 (n + 1) 或 n + 1