树

概念

非线形结构，每个元素可以有多个前驱和后继

结点

树中的数据元素

degree 度

结点拥有的子树的数目，记作d

叶子结点 leaf

结点的度为0， 称为叶子结点leaf， 终端结点，末端结点

分支结点

结点的度部位0，称为非终端结点或分支结点

分支

结点之间的关系

内部结点

除根结点外的分支结点，当然也不包括叶子结点

树的度是树内个结点的度的最大值

子结点 Child Node

结点的子树的根结点成为该结点的孩子

双亲结点 Parent Node

一个接的是他各子树的根结点的双亲

兄弟结点 Sibling Node

具有相同双亲结点的结点

祖先结点

从根结点到该结点锁经分支上所有的结点

子孙结点

结点的所有子树上的结点

结点层次 Level

根结点为第一层

根结点的孩子为第二层

以此类推

树的深度 Depth

树的层次的最大值

有序树

结点的子树是有顺序的，不能交换

无序树

结点的子树是无序的，可以交换

路径

树中的k个结点n1，n2 …… nk 满足nx是n(x+1) 的双亲，成为n1到nk的一条路径，一条线串下来，前一个都是后一个父结点

森林

m(m>=0) 棵不相交的树的集合

对于结点而言，子树的集合就是森林

树的特点

唯一的根

子树不相交

除了根以外，每个元素只能有一个前驱，可以有零个或者多个后继

根结点没有双亲结点，叶子结点没有孩子结点

二叉树 Binary Tree

定义

每个结点最多2棵子树

二叉树不存在度数大于2的结点

形态

空二叉树

只有一个根结点

根结点只有左子树

根结点只有右子树

根结点有左子树和右子树

二叉树性质

在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

深度为k的二叉树，至多有(2^k)-1个结点(k>=1)

任何的二叉树，如果其终端结点数为n0，度数为2的结点为n2，则n0=n2+1

高度为k的二叉树，至少有k个结点

左斜树

所有结点只有左子树

右斜树

所有结点只有右子树

满二叉树

深度为3的7结点满二叉树

      a
    /   \
   b     c
  /\     /\
d   e   f   g

定义

一颗二叉树的所有分支结点都存在左子树和右子树，并且所有叶子结点只存在在最下面一层

特点

同样深度二叉树中，满二叉树结点最多

完全二叉树

定义

若二叉树的深度为k，二叉树的层数从1到k-1层的结点数都达到了最大个树，并且在第k层的所有结点都集中在最左边

        a
      /   \
     b     c
    /\     /\
  d   e   f   g
 /
h

        a
      /   \
     b     c
    /\     /\
  d   e   f   g
 /\
h   i

        a
      /   \
     b     c
    /\     /\
  d   e   f   g
 /\   /\  /
h  i j  k l

特点

完全二叉树由满二叉树引出

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

具有n个结点的完全二叉树的深度为math.ceil(log2(n+1))

二叉树遍历

对树中所有的元素不重复地访问一遍，也称扫描

层序遍历

按照层次，从第一层开始，自左向右遍历元素

前序遍历

从根结点开始，自左子树，后右子树

中序遍历

从根结点的左子树开始遍历，然后是根结点，再右子树

后序遍历

先左子树，然后右子树，再根结点