目录

概念

结点分类

根结点

结点的度（De-gree）

树的度

结点间关系 

孩子（Child）、双亲（Parent）

 兄弟（Sibing）、堂兄弟（Cousins）

祖先（ancestor)、 子孙（descendant）

结点的层次（Level）、树的深度（Depth）

有序树、无序树、森林（Forest）

总结

线性结构和树结构的差异

---

概念

• 树（Tree）是 n(n >= 0) 个结点的有限集
  • 若 n = 0 为空树
  • 若 n > 0
    • 有且仅有一个特定的，称为根（Root）的结点
    • 其余结点可分为 m(m >= 0) 个互不相交的有限集T₁，T₂，...，Tₙ，其中每一个集合本身又是一棵树，称为根的子树（SubTree）

结点分类

根结点

• 非空树中无前驱结点的结点

---

结点的度（De-gree）

• 结点拥有的子树的个数
• 度为0的结点称为叶结点（Leaf）或终端结点
• 度不为0的结点称为非终端结点或分支结点
  • 除了根结点之外，分支结点又称为内部结点

---

树的度

树内各结点的的度的最大值

---

结点间关系 

孩子（Child）、双亲（Parent）

• 结点的子树的根称为该结点的「孩子」（Child）
  • D为B的「孩子」
• 该结点称为「孩子」的「双亲」（Parent）
  • B为D的「双亲」

---

 兄弟（Sibing）、堂兄弟（Cousins）

• 同一个「双亲」的「孩子」之间互称为「兄弟」（Sibling）
  • B和C互为「兄弟」
• 「双亲」在同一层的结点互称为「堂兄弟」
  • D和E互为「堂兄弟」

---

祖先（ancestor)、 子孙（descendant）

 

• 结点的「祖先」（ancestor）：从根到该结点所经分支上的所有结点
  • A、C 都是 F 的「祖先」（Ancestor）
  • F 是所有这些结点的「子孙」（Descendant）

---

结点的层次（Level）、树的深度（Depth）

• 结点的层次从根开始定义，根为第一层，根的「孩子」为第二层
  • 若某结点在第 n 层，则其子树就在第 n + 1 层
• 树中结点的最大层次称为树的深度或树的高度

---

有序树、无序树、森林（Forest）

• 有序树：树中结点的各子树从左至右有次序
• 无序树：树中结点的各子树无次序
• 森林（Forest）：是 m(m >= 0）棵互不相交的树的集合

• 只有一棵树，是森林

---

• 有两棵树，是森林

总结

• 一棵树可以看成是一个特殊的森林
• 给森林中的各子树加上一个「双亲」结点，森林就变成了树

线性结构和树结构的差异

线性结构	树结构
第一个数据元素：无前驱	根结点（只有一个）：无双亲
最后一个数据元素：无后继	叶结点（可以多个）：无孩子
中间元素：一个前驱、一个后继	中间结点：一个双亲、多个孩子
一对一	一对多

---

二叉树（Binary Tree） 

二叉树特点

• 每个结点最多有两棵子树（二叉树中不存在「度」大于2的结点）
• 子树有左右之分，其次序不能颠倒
• 二叉树可以是空集，根可以有空的左子树或空的右子树

---

二叉树不是「树」（的特殊情况）

• 二叉树是树型结构，但「二叉树」是「树」是两种不同的数据结构
• 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要区分，说明它是左子树，还是右子树
• 树当结点只有一个「孩子」时，就无须区分它和左还是右的次序。因此，二者不同

• 二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置
• 而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了

---

 二叉树的5种基本形态

---

二叉树的性质

• 在二叉树的第 i 层上最多有 2ⁱ⁻¹ 个结点（i >= 1），最少 1 个结点
• 深度为 k 的二叉树最多有 2ᵏ - 1 个结点（k >= 1），最少 k 个结点
• 对任何一棵二叉树，如果其终端结点数为 n₀，度为2的结点数为 n₂，则 n₀ = n + 1
• 具有n个结点的完全二叉树的深度为[log₂n] + 1(高斯取整)

• 如果对一棵有n个结点的完全二叉树的结点按层序编号，对任意结点i有：

  • 如果 i = 1，则i是二叉树的根，无双亲；如果 i > 1，则双亲为[i / 2]
  • 如果 2i > n，则结点i是叶子结点，否则其左孩子是结点 2i
  • 如果 2i + 1 > n,则结点i是叶子结点，否则其右孩子为 2i + 1

---

特殊二叉树 

斜树

• 左斜树

---

• 右斜树

---

满二叉树

• 一棵深度为 k，且二叉树最多有 2ᵏ - 1 个结点的二叉树
• 特点
  • 每一层上的结点数都是最大结点数，即每层都满
  • 叶子结点全在最底层

---

完全二叉树 

• 对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i(1 <= i <= n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满的
• 特点
  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数二层，若有叶子结点，一定都在右部连续位置
  • 如果结点度为1，则该结点只有左「孩子」，即不存在只有右子树的囚；
  • 同样结点数的二叉树，完全二叉树的深度最小

• 完全二叉树

---

• 非完全二叉树 

• 树1，结点5没有左子树，却有右子树，使得按层序编号的第10个编号空挡了
• 树2，结点3没有子树，使得6、7编号的位置空挡了

二叉树的抽象数据类型定义 

ADT Tree{
Data 
    树是由一个根结点和若干棵子树构成的。树中结点具有相同的数据类型及层次关系。
Operation
    InitTree(*T) :构造空树T
    DestroyTree(*T): 销毁树
    CreateTree(*T, definition):按definition中给出树的定义来构造树
    ClearTree(*T): 清空树
    TreeEmpty(*T): 空树返回true
    TreeDepth(*T): 返回T的深度
    Root(*T): 返回T的根结
    Value(T, cur_e): cur_e是树T中的一个结点，返回此结点的值
    Assign(T, cur-e, value): 给树T的结点cur_e赋值为value
    Parent(T, cur_e): 若cur_e不是根结点，则返回它的双亲
    LeftChild(T, cur_e): 若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空。
    RightSibling(T, cur_e): 若cur_e有右兄弟，则返回右兄弟，否则返回空。
    InsertChild(*T, *p, i, c):其中p指向树T的某个结点，i为所指结点p的度加上1，若非空树c与T不相交，操作结果为插入c为树T中p指向结点的第i棵子树。
    DeleteChild(*T, *p, i): 其中p为指向树T的某个结点，i为所指结点p的度，操作结果为删除T中P所指向结点的第i棵子树。
}endADT