§7 树§7.1 树的概念【定义】 树（Tree）是 n（n>0）个结点的有限集合 T，它满足如下两个条件：(1) 有且仅有一种特定的称为根（Root）的结点；(2) 其他的结点可分为 m（m≥0）个互不相交的有限集合，其中每一种集合又都是一颗树，并称为根的子树（Sub Tree）。【基本术语】k1.树的结点包含一种数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度（degree）。如图 7.1，A 的度为 3，C 的度为 1，F 的度为 0。2.度为 0 的结点称为叶子（leaf）或终端结点。例如 K、L、F、G、M、I、J。度不为 0 的结点称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。3.树的度是树内各结点的度的最大值，如图 7.1 中树的度为 3。4.结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲（parent）。如图，B 为 A 的子树的根，则 B 是 A 的孩子，而 A 则是 B 的双亲。同一种双亲的孩子之间互称为兄弟（sibling），例如 B、C、D 互为兄弟。将这些关系深入推广，可认为 D 是 M 的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如，M 的祖先为 A、D、H。反之，结点的子树中的任一结点都称为该结点的子孙，如 B 的为 E、F、K、L。5. 结点的层次（level）是从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 x 层，则其子树的根就在 x+1 层。树中结点的最大层次称为树的高度或深度（depth）。如图 7.1 的树的深度为 4。6. 假如将树中的结点的各子树当作从左到右是有次序的（即不能互换），则称该树为 有序树,否则称为无序树。如图。 7.森林（forest）是 m（m≥0）棵互不相交的树的集合。§7.2 二叉树§ 二叉树的定义 图 图 两棵不一样的有序树 图二叉树（binary tree）是一种树型构造，它的每个结点至多只有二棵子树（即二叉树中不存在度不小于 2 结点），并且，二叉树的子树有左右之分，另一方面序不能任意颠倒。（如图） 满二叉树和完全二叉树是两种特殊形态的二叉树。 满二叉树是指深度为 k，且有 2k-1 个结点的二叉树。 完全二叉树是指深度为 k，有 n 个结点，当且仅当每一种结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时。§ 二叉树的性质性质 1：在二叉树的第 i 层上至多有 ① 个结点（i≥1）。性质 2：深度为 k 的二叉树至多有 ② 个结点（k≥1）。性质 3：对任意一棵二叉树，假如度...
