数据结构基础：树和二叉树

一、树的基本概念

1. 定义

树是 n（n >= 0）个结点的有限集合。

• n = 0 时：称为空树。
• n > 0 时，满足：
  • 有且仅有一个根结点（root）
  • 其余结点可分为 m（m>0）个互不相交的有限集合，每个集合本身也是一棵树，称为根的子树

2. 结点的分类

1. 结点：树中的一个独立单元，包含一个数据元素，及若干指向其子树的分支。
2. 度（结点的）：子树的个数。
3. 树的度：结点中最大的度。
4. 叶子节点（终端节点）：度为 0 的节点。
5. 分支节点（内部节点或非终端节点）：度不为 0。

3. 节点之间的关系

1. 双亲和孩子：结点的子树称为该结点的孩子，该结点也称为孩子的双亲。
2. 兄弟：同一个双亲的孩子之间互称兄弟；双亲在同一层的孩子称为堂兄弟。
3. 祖先和子孙：结点的祖先是从根到该结点所经分支上的所有结点，以某结点为根的子树中的任一结点称为该结点的子孙。

4. 度量树

• 树的深度：树中的结点的最大层次。
• 树的高度：两者之间数值相同。