树
- 非线性结构
- 树是n(n >= 0)个元素的集合:
- （1）每个元素称为结点（node）；
- （2）有一个特定的结点，称为根结点或根（root）；
- （3）除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树Subtree）
- 注意
- n = 0时，称为空树
- 树只有一个特殊的没有前驱的元素，称为树的根（Root）
- 树中除了根结点外，其余元素只能有一个前驱，可以有零个或多个后继
- 子树也有自己的根
树的概念
- 结点（node）：树中的数据元素
- 结点的度（degree）：结点拥有的子树的数目称为度（该结点的分支数），记作d(v)
- 叶子结点：结点的度为0，称为叶子结点leaf、终端结点、末端结点
- 分支结点：结点的度不为0，称为非终端结点或分支结点
- 分支：结点之间的关系
- 内部结点：除根结点外的分支结点，也不包括叶子结点
- 树的度是树内各结点的度的最大值。 D子树的度就是3
- 孩子结点（Child）：
- B是A的孩子
- 双亲结点（Parent）：
- C是E,F的双亲
- 兄弟结点（Sibling）：
- 具有相同双亲结点的结点
- B和C是兄弟
- 祖先结点:
- 从根结点到该结点所经分支上所有的点
- A,B,D都是G的祖先结点
- 子孙结点：
- 结点的所有子树上结点都称为该结点的子孙
- C的子孙是E,F,J
- 结点的层次（level）：
- 根结点为第一层，根的孩子为第二层，以此类推，记作L(v)
- 树的深度（高度Depth）：
- 树的层次的最大值
- 上图树深度为4
- 堂兄弟：
- 双亲在同一层的结点
- D,E或F是堂兄弟
- 有序树
- 结点的子树是有顺序的（兄弟有大小，先后次序）
- 无序树
- 结点的子树是无序的，可以交换
- 路径
- 一条线串下来的，前一个都是后一个的双亲结点
- 路径长度 = 路径上的结点数 – 1 ，也是分支数
- 森林
- m（m>=0）颗不相交的树的集合
- 对于结点而言，其子树的集合就是森林。
- A结点的2颗子树的集合就是森林
树的特点
- 唯一的根
- 子树不相交
- 除根以外，每个元素只能有一个前驱，可以有零个或多个后继
- 根结点没有双亲，叶子结点没有孩子
- vi是vj的双亲，则L(vi) = L(vj) – 1, 也就是说双亲比孩子结点的层次小1
- 堂兄弟的双亲未必是兄弟，例如I,J是堂兄弟，而他们的双亲也是堂兄弟
二叉树
- 每个结点最多2颗子树
- 二叉树不存在degree > 2 的结点
- 是有序树，左子树、右子树是顺序的，不能交换次序
- 即使某个结点有一颗子树，也要确定是左子树还是右子树
- 二叉树的五种基本形态
- 空二叉树
- 只有一个根结点
- 根节点只有左子树
- 根节点只有右子树
- 根节点只有左子树和右子树
斜树
- 左斜树，所有结点都只有左子树
- 右斜树，相反
满二叉树
- 一颗二叉树的所有分支结点都有左右子树，并且所有叶子结点都在最下面一层
- 同样深度二叉树中，满二叉树结点最多
- k为深度，则结点总数为2**k-1
- 如下图，深度为4的15个结点的满二叉树
完全二叉树Complete Binary Tree
- 除了最后一层的所有的结点都集中在最左边，其他层都是满的
- 完全二叉树有满二叉树引出
- 区别在于他们的最后一层，完全二叉树最后一层的结点可以不满
二叉树的性质
1.在二叉树的第i层上最多有2**(i-1)个结点
2.深度为 k 的二叉树，最多有 2**k-1 个结点
3.对任何一颗二叉树，如果其终端结点数为n0,度数为2的结点数为n3，则有n0 = n2 + 1
- 换句话说，就是叶子结点数 -1 就等于度数为2 的结点数
- 证明
4.其他性质
- 高度为k的二叉树，至少有k个结点
- 含有n个的结点的二叉树的高度之多为n，最小为
math.ceil(log2 (n+1))
5.具有n个结点的完全二叉树的深度为 int(log 2 n) + 1或者math.ceil(log2 (n+1))
6.如果有一颗n个结点的完全二叉树，结点按照层序编号，如下图
- 如果i = 1，则结点i是二叉树的根
- i > 1，双亲是int(i/2），这是向下取整
- 双亲结点是 i, 左孩子结点就是 2i， 右孩子结点就是 2i+1
- 2i > n，则结点 i 无左孩子，即结点i为叶子结点；否则其左孩子结点存在，编号为2i
- 2i+1 > n，则结点 i 无右孩子；这里不能说明结点i没有左孩子。否则其右孩子结点存在，编号为2i+1
本文来自投稿，不代表Linux运维部落立场，如若转载，请注明出处：http://www.178linux.com/87842
