树

树：

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

树时n(n>=0)个元素的集合

     当n=0时 称为空树

     树只有一个特殊的没有前驱的元素，成为树的根ROOT

     树中除了根节点外，其余元素只能有一个前驱，可以有零个或多个后继

 

递归定义

     树T时n(n>=0)个元素的集合，n=0时，称为空树

     有且只有一个特殊元素跟，剩余元素都可以被划分为M个不相交的集合T1 T2 T3而每一个集合都是树，称为T的子树Subtree

     子树也有自己的根

 

树的概念：

 结点： 树中的数据元素

结点的度degree： 结点拥有的子树的数目称为度，记作d(v)

叶子结点：结点的度为0，称为叶子结点leaf、

分支结点： 结点的度不为0，称为非终端结点或分支结点

分支： 结点之间的关系

内部结点：除根节点外的分支结点，当然不包括叶子结点

树的度时书内各结点的度的最大值

 

孩子（儿子child）结点：结点的子树的根结点称为该结点的孩子

双亲（父parent）结点：一个结点是它各个子树的根节点的双亲

兄弟（sibling）结点： 具有相同双亲的结点

祖先结点：从根节点到该结点所经分支上所有的结点，ABD都是G的祖先结点

子孙结点： 结点的所有子树上的结点都成为该结点的子孙，b的子孙时DGHI

结点的层次（level）：根结点为第一层，根的孩子为第二层，依次类推，记作l(v)

树的深度（高度Depth）：树的层次的最大值，上图的树的深度为4

堂兄弟： 双亲在同一层的结点

 

有序树： 结点的子树时有顺序的（兄弟有大小，有先后顺序）不能交换

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

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

路径长度=路径长度结点树-1，也就是分支树

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

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

 

树的特点：

     唯一的根

     子树不相交

     输了根意外，每个元素只有有一个前驱，可以有0个或多个后继

     根节点没有双亲结点（前驱），叶子结点没有孩子结点（后继）

     vi是vj的双亲，则l(vi)=l(vj)-1，也就是说双亲比孩子的层次结点小1

 

二叉树：

每个结点最多2个子树

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

 它是有序树，左子树，右子树是顺序的，不能交换顺序

即使某个结点只有一棵子树，也要确定它是左子树还是右子树

 

二叉树的五种形态：

     空二叉树

     只有一个根节点

     根节点只有左子树

     根节点只有右子树

     根节点有左右子树

 

斜树：

左斜树：所有结点只有左子树

右斜树：相反

 

满二叉树：

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

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

k为深度(1<=k<=n），则结点总数为 2^k-1

如下图一个深度为4 的15个结点的满二叉树：

 

 

完全二叉树：

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

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

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

k为深度（1<=k<=n）则结点总数最大值为2^k-1，当达到最大值的时候就是满二叉树

 

完全二叉树：

如下图，所有叶子结点都连续的集中在左边

 

完全二叉树图二：

 

完全二叉树图3：

 

不是完全二叉树，如下图：

 

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

换言之就是 叶子节点数-1就等于度数为2的结点数

 

二叉树的性质：

其他性质：

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

含有n(n>=1)的结点的二叉树高度最多为n，同上句

含有n(n>=1)的结点的二叉树的高度最多为n最小为 math.ceil(log2(n+1))， 不小于数值的最小整数，向上取整

 

 具有n个结点的完全二叉树的深度为int(log2n)+1或者mathh.ceil(log2(n+1))

 

性质5：