树
介绍
- 非线形结构，每个元素可以有多个前驱和后继
树是n(n>=1)个元素的集合
- n = 0时，称为空树
- 树只有一个特殊的没有前驱的元素，称为树的根Root
- 树中除了根节点外，其余元素只能有一个前驱，但可以有0个或者多个后继
递归定义
- 树T是n(n>=0)个元素的集合，当n=0时，称为空树
- 有且只有一个特殊元素根，剩余元素都可以被划分为m个互不相交的集合T1、T2、T3，而每一个集合都是树，称为T的子树Subtree
- 子树也有自己的根
树的概念
结点：树中的数据元素
结点的度degree：结点拥有的子树的数目称为度，记做d(v)
叶子结点：结点的度为0，也就是没有子树的，也称为终端结点，末端结点
分支结点：结点的度不为0，称为非终端结点或分支结点
分支：结点之间的关系
内部结点：除根节点之外的分支结点，当然也不包括叶子结点。掐头去尾
树的度是树内各结点的度的最大值，D结点度最大为3，树的度数就是3
子结点：结点的子树的根结点称为该结点的孩子
父结点：一个结点是它各子树的根节点的父结点
兄弟结点：具有相同父结点的结点
祖先结点：从根结点到该结点所经分支上所有的结点，A、B、D都是G的祖先结点
结点的层次：根节点为第一层，根节点的子结点为第二层，记作L(v)
树的深度(高度Depth)：树的层次的最大值，上图深度为4
有序树：结点的子树是有顺序的，不能交换
无序树：结点的子树是无序的，可以交换
路径：树中的k个结点n1、n2…nk，满足ni是n(i+1)的父结点，成为n1到nk的一条路径，就是一条线串下来的
路径长度=路径上结点树-1，也是分支数
森林：m(m>=0)颗不相交树的集合就是森林
- 对于结点而言，其子树的集合就是森林，A结点的2颗子树的集合就是森林。
树的特点
- 有唯一的根
- 子树不相交
- 除了根以外，每个元素只能有一个前驱，可以有0个或者多个后继。
- 根节点没有父结点（前驱），叶子结点也没有子结点（后继）。
二叉树
每个结点最多2颗子树
- 二叉树不存在度数大于2的结点
- 它是有序树，左子树、右子树是顺序的，不能交换次序。
- 即使某个结点只有一棵树，也要确定它是左子树还是右子树
二叉树的五种基本形态
- 空二叉树
- 只有一个跟结点
- 根节点只有左子树
- 根节点只有右子树
- 根节点有左子树和右子树
满二叉树
- 一颗二叉树的所有分支结点都存在左子树和右子树，并且所有叶子结点只存在在最下面一层。
- 同样深度的二叉树中，满二叉树结点最多。
- k为深度（1<=k<=n），则结点总数为2^k-1
- 如下图，一个深度为4的15个结点的满二叉树
完全二叉树
- 若二叉树的深度为k，二叉树的层数从1到k-1层的结点树都达到了最大个数，在第k层的所有结点都集中在最左边，就是完全二叉树
- 完全二叉树由满二叉树引出
- 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
- k为深度（1<=k<=n），则结点总数最大值为2^k-1，当达到最大值的时候就是满二叉树
二叉树性质
在二叉树的第i层上，至多有2^(i-1)个结点（i>=1）
深度为k的二叉树，至多有2^k-1个结点（i>=1）
对任何一个二叉树T，如果其终端结点数为n0，度数为2的结点为n2，则有n0=n2+1
- 就是叶子节点数-1等于度数为2的节点数
高度为k的二叉树，至少有k个结点。
含有n个结点的二叉树高度至多为n。最小为math.ceil(log2(n+1))，不小于对数值得最小整数，向上取整。
- 假设高度为h，2^h-1=n => h = log2(n+1)，层次数取整，如果是8个结点，3.1399向上取整为4层。故8节结点最小为4层，最多为8层。
具有n个结点的完全二叉树的深度为int(log2n)+1或者math.ceil(log2(n+1))
如果有一颗n个结点的完全二叉树，层序如下图
- 如果i=1，则结点i是二叉树的根，无父结点。
- 如果i>1，则其父结点是int(i/2)，向下取整，就是子节点的编号整除2得到的就是父结点的编号，父结点如果是i，那么左子结点就是2i，右子节点就是2i+1
- 如果2i>n，则结点i无左子结点，即结点i为叶子结点，否则其左子结点存在编号为2i
- 如果2i+1>n，则结点i无右子结点，注意这里并不能说明结点i没有左子结点，否则右子结点存在编号为2i+1。
若有收获，就点个赞吧
0 人点赞
