13.树

树

01.树是非线性结构，每个元素可以有多个前驱和后继。

• 树是n(n>=0)个元素的集合：
  • n等于0时，称为空树。
  • 树只有一个特殊的没有前驱的元素，称为树的根Root。
  • 树中除了根节点外，其余元素只能有一个前驱，可以有0个或多个后继。
• 树的概念包括：
  • 结点，树中的数据元素。
    • 孩子结点，结点的子树的根结点称为该结点的孩子。
    • 双亲结点，一个节点是它各子树的根结点的双亲。
    • 兄弟结点，具有相同双亲结点的结点。
    • 祖先结点，从根结点到该结点所经分支上所有的节点。
    • 子孙结点，结点的所有子树上的结点都称为该节点的子孙。
  • 结点的度（degree），结点拥有的子树的数目称为度，记做d(v)。
    • 树的度是树内各结点的最大度；结点度最大为4，树的度数就是4。
    • 叶子结点，度为0的结点。
    • 分支结点，度不为0的结点。
  • 分支，结点之间的关系。
  • 内部结点，除根节点外的分支结点，也不包括叶子结点。
  • 有序树，结点的子树是有顺序的，（兄弟有大小，有先后次序），不能交换。
  • 无序树，结点的子树是有无顺序的，可以交换。
  • 路径，树中的k个结点n1、n2 … nk，满足ni是n(i+1)的双亲，称为n1到nk的一条路径；即前一个结点都是后一个结点的父结点。
    • 路径长度，路径长度是路径上的结点数-1，也是分支数。
  • 森林，m(m>=0)颗不相交的树的集合称为森林。
    • 对于结点而言，其子树的集合就是森林。
• 树的特点包括：
  • 唯一的根。
  • 子树不相交。
  • 除了根以外，每个元素只能有一个前驱，可以有0个或多个后继。
  • 根节点没有双亲结点（前驱），叶子结点没有孩子节点（后继）。
  • vi是vj的双亲，则L(vi)=L(vj)-1，也就是说双亲比孩子结点的层次小1。
• 树的示例：

02.二叉树：

• 每个结点最多2棵子树的树称为二叉树。
• 二叉树是有序树，左子树，右子树，不能交换次序。
  • 即使某个结点只有一棵子树，也要确定它是左子树还是右子树。
• 二叉树的五种基本形态：
  • 空二叉树。
  • 只有一个根结点。
  • 根结点只有左子树。
  • 根结点只有右子树。
  • 根节点有左子树和右子树。
• 斜树：

• 左斜树，所有结点都只有左子树。
• 右斜树，所有结点都只有右子树。
• 满二叉树：

• 一棵二叉树所有分支结点都存在左子树和右子树，并且所有叶子结点只存在在最下面一层。
• 同样深度的二叉树中，满二叉树结点最多。
• k为深度(1<=k<=n)，则结点总数为2^k-1。
• 完全二叉树：

• 若二叉树的深度为k，二叉树的层数从1到k-1层的结点都达到了最大个数，在第k层的所有节点都集中在最左边，称为完全二叉树。
• 满二叉树一定是完全二叉树，完全二叉树不是满二叉树。

03.二叉树的特性：

• 性质1：

• 在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
• 性质2：
  • 深度为k的二叉树，至多有2^k-1个结点（k>=1）。
  • 深度为k的二叉树，至少有k个结点（k>=1）。
• 性质3：
  • 对于任意一棵二叉树T，如果其终端结点数为n0，度数为2的结点为n2，，则n0=n2+1。
  • 叶子结点数-1等于度数为2的结点数。
• 性质4：
  • 具有n个节点的完全二叉树深度为int(log2n)+1。
• 性质5：

• 如果有一棵n个结点的完全二叉树，结点按照层序编号（如上图），则：
  • 如果i=1，则结点1是二叉树的根；如果i>1，则其双亲是int(i/2)，向下取整。
  • 如果2i>n，则结点i无左孩子，即节点为叶子结点；否则其左孩子结点存在编号为2i。
  • 如果2i+1>n，则节点i无右孩子，注意这里并不能说明节点i没有左孩子；否则有孩子节点存在编号为2i+1。