五、树与二叉树

1. 树的基本概念

1.1 树的定义

树是n个结点的优先级。当n=0时，称为空树。任意非空树应该满足：

1. 有且只有一个特定的称为根的结点
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集$T_1$T1​、$T_2$T2​、$T_3$T3​…$T_m$Tm​，其中每个集合本身又是一个树，并且称为根的子树。

树的定义是递归的，即在树的定义中有用到了其自身，所以树是一种递归的数据结构。树作为一种逻辑结构，同时也是分层结构，具有以下特点：

1. 树的根结点没有前驱，除根结点外的所有节点有且只有一个前驱。
2. 树中所有结点可以有0个或者多个后继。

树中的某个结点(除根结点外)最多只和上一层的一个结点(父节点)有直接关系，根结点没有直接上层结点，所以n个结点的树有n-1条边。树中每个节点与下一层的0个或者多个结点(子女结点)有直接关系。

1.2 基本术语

• 祖先结点：根结点到某结点的唯一路径上的任意结点。A、B是E的祖先。
• 子孙结点：从某结点出发，其所有路径上的所有结点都是该结点的子孙结点。E是A、B的子孙。
• 双亲结点(父节点)：一个结点的直接前驱结点。B是E的双亲结点。
• 孩子结点：一个结点的直接后继。E是B的孩子结点。
• 兄弟结点：有相同双亲的结点称为兄弟结点。E、F是兄弟结点。
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟。E、F、G、H、I、J是堂兄弟结点。

---

• 路径：树的两个结点之间所经过结点序列，树的分支是有方向的，即从双亲到孩子(从上到下)，所以同一双亲的两个孩子之间不存在路径。
• 路径长度：路径上所经过的边的个数。

---

树与结点的属性：

• 结点的深度：自根结点开始自顶向下逐层累加。
• 结点的高度：自叶结点开始自底向上逐层累加。
• 树的高度(深度)：树中结点的最大层数。
• 结点的度：有几个孩子(分支)。
• 树的度：各结点的度的最大值。
• 分支结点(非终端结点)：度大于0的结点。
• 叶子结点(终端结点)：度为0的结点。

---

有序树和无序树：

• 有序树：逻辑上看，树中结点的各子树从左到右是有次序的，不能互换。
• 无序树：逻辑上看，树中结点的各子树从左到右树无次序的，可以互换。

---

森林：森林是m(m>=0)棵互不相交的树的集合，特别地，m为0为空森林。

1.3 树的性质

• 性质1：结点数=总度数+1.
• 性质2：度为m的树中第i层上至多有$m^{i-1}$mi−1个结点(i>=1)。
• 性质3：高度为h的m叉树至多有($m^h-1$mh−1)/(m-1)个结点，至少有h个结点。高度为h的度为m的树至多有($m^h-1$mh−1)/(m-1)个结点，至少有h+m-1个结点。
• 性质4：具有n个结点的m叉树的最小高度为[$log_m(n(m-1)+1)$logm​(n(m−1)+1)]。

注意：度为m的树，m叉树的区别：
二者都要满足任意结点的度<=m，即最多m个孩子。但是前者至少需要一个结点的度为m，后者允许所有结点的度都<m。前者一定是非空树，至少m-1个结点，后者可以是空树。