大话数据结构十三：二叉树的链式存储结构（二叉链表）

大话数据结构十三：二叉树的链式存储结构（二叉链表）2014-12-301. 关于树

① 树的度 — 也即是宽度，简单地说，就是结点的分支数。

② 树的深度 — 组成该树各结点的最大层次。

③ 森林 — 指若干棵互不相交的树的集合。

④ 有序树 — 指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

2. 二叉树的特点

i、每个结点最多有两颗子树

ii、左子树和右子树是有顺序的，次序不能任意颠倒

iii、即使树中某结点只有一颗子树，也要区分它是左子树还是右子树

3. 二叉树五种形态

① 空二叉树

② 只有一个根结点

③ 根结点只有左子树

④ 根结点只有右子树

⑤ 根结点既有左子树又有右子树

4. 特殊的二叉树

① 斜树：所有的结点都只有左子树的二叉树叫左斜树，所有的结点都只有右子树的二叉树叫右斜树，这两者统称为斜树。

② 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。