二叉树的概念:
二叉树是树的一种,二叉树是一个节点,最多只有两个子节点,二叉树是一个特殊的树二叉树的度最大为2
从上图可得一棵二叉树是结点的一个有限集合,该集合:
- 或者为空
- 由一个根结点加上两棵别称为左子树和右子树的二叉树组成
二叉树的分类:
- 二叉树分为完全二叉树和满二叉树。
满二叉树:
在二叉树的基础上,在规定的层数中,每一层都保持了最大的度,或者说每一层都是排满了结点。
- 如上图所示,在满二叉树中,结点的个数和二叉树的高度是一个等差数列的关系。
完全二叉树:
满二叉树的演变如果是H的层数,那么H-1层是满的,而最后一层不一定是满的,如下图所示。
错误案例:
完全二叉树的高度和结点关系:
- 由于完全二叉树的最后一层是不确定的,所以完全二叉树的结点个数其实是一个动态区间关系
- 而假设完全二叉树的高度是h,那么h-1层的结点个数和满二叉树的结点个数算法一致
- 而最后一层的结点个数根据推论是在1到 2^(h-1)之间
- 所以完全二叉树的结点个数和高度关系是:[:2^(h-1), 2^h-1]
- 完全二叉树的结点个数也是[:2^(h-1), 2^h-1]
二叉树的存储方式:
数组存储:
如图所示,数组存储是一层一层的进行存储,先左后右先上后下,而数组存储只能适用于满二叉树。
如果存储到数组中,怎么找到孩子结点对于的下标呢?
- 左孩子结点的下标 = 父亲结点的下标 * 2 +1 ,右孩子结点下标 = 父亲结点的下标 * 2 +2
知道孩子怎么算父亲节点下标?
- (孩子结点的下标-1 ) / 2
未完待续...........................................