树的算法基础知识

什么是树：

树是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：

• 有且仅有一个特定的称为根的结点
• 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、......、Tm，其中每一个集合本身又是一棵树，并且称为根的子树
• 树的度：即选取整个树中，出现最大分支的数量为整个树的度
• 结点间的关系：左右分支称为结点的孩子，而结点称为左右分支的双亲，左右分支又互称为兄弟，祖先则是表示从根到该节点所经分支上的所有结点，同一层结点但不同分支称为堂兄弟。

  树的表示：

  双亲表示法：                                               data  |   parent

  

  其中parent列用双亲的编号表示

  孩子表示法：                           data | child1 | child2 | child3 | ..... | childn

  

  下图是链表表示方法：

  

  孩子双亲表示法：以上图为基础加上一列表示双亲编号

  

  孩子兄弟表示法：                           data | firstchild | rightsilb

  

  二叉树：

  二叉树是n（n>=0）个结点的有限集合（最多有两个结点），该集合或者为空集（称为空二叉树）。或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

  特殊二叉树：

  斜树：呈现出来是一条直线的树

  满二叉树：

  完全二叉树： 叶子从左向右排序的形态

  用数组表示：

  • 推论：对于位置为K的结点 左子结点=2*k+1，右子结点=2*（k+1）
  • 推论：最后一个非叶结点的位置为（N/2）-1，N为数组长度

    二叉树表示：

    data | leftchild | rightchild