树与二叉树
在了解二叉树之前，我们应该首先了解一些树的概念，以便我们能够理解二叉树。
什么是树？
树(英语:tree)是抽象数据类型(ADT)或者用这种抽象数据类型的数据结构来模拟具有树状结构性质的数据集。
它是由n(n>=1)一个有限的节点形成一个具有层次关系的集合。它被称为“树”，因为它看起来像一棵倒挂的树，也就是说，它的根朝上，叶子朝下。它具有以下特点：
每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每个非根节点都有，只有一个父节点；
除根节点外，每个子节点可分为多个不相交的子树；
树的术语：
节点的度: 节点中子树的数量称为节点的度；
树的度: 在一棵树中，节点的度称为树的度；
根结点： 树顶的节点继续分为子节点
父节点： 子节点的上一层是父节点
兄弟节点： 具有相同父节点的节点称为兄弟节点
叶片节点/终端节点： 不再有子节点的节点是叶节点
二叉树：
二叉树是一种特殊的树，具有以下特点：
每个节点最多有两棵子树，节点度为2
左右树是有序的，顺序不能颠倒
也就是说，一个节点只有一棵子树，左右子树也要区分
二叉树的性质：
非空二叉树的第一层最多有2i-1个节点(i>=1)
深度为K的二叉树最多有2k-1个节点(k>.1)
对于任何一棵非空二叉树，如果叶节点数为n0，度数为2，则有n0=n2+1
推倒过程:在二叉树中，除了叶节点(度为0)外，只剩下度为2(n2)和度为1(n1)的节点。那么树的节点总数是T = n0 + n1 + n2；二叉树中的节点总数为T，而连接总数为T-1 = 2*n2 + 因此，有：n0 + n1 + n2 - 1 = 2 *n2 + n1，获得n0=n2+1。
特殊的二叉树
满二叉树
在二叉树中，除叶节点外，所有其他节点都是2度，所有的叶节点都在同一层，这样的二叉树变成了满二叉树。
满二叉树的特点：
叶节点只能出现在下一层
非叶节点度数必须为2
在同一深度的二叉树中，满二叉树节点最多，叶节点最多
完全二叉树
如果将最后一层叶节点从二叉树中去除，最后一层叶节点从左到右依次分布，则这种二叉树称为完全二叉树
完全二叉树的特点：
叶节点通常出现在下一层。如果倒数第二层出现叶节点，则必须出现在右连续位置
下叶节点必须集中在左边的连续位置
同节点的二叉树深度最小(满二叉树也是对的)
小例题：
一棵完整的二叉树有200个节点，其中有一个()叶节点？
解：n0 + n1 + n2 = 200， 其中n0 = n2 + 1，n1 = 0或者1 (n1=1，最下一层节点数为奇数，最下一层节点数为偶数，则n1=0)， 因为n0是整数，所以最终计算n0 = 100。
完全二叉树的性质：
log2n+1是完全二叉树的深度，有n个节点。log2n结果取整数部分。
如果有一个有n个节点的完全二叉树的节点按层次顺序编号，任何一层的节点i(1) <= i <= n)
1. 如果i=1，节点是二叉树的根，没有父节点，如果i=1>1.父节点为i/2，向下取整
2. 如果2*1>n，所以节点i没有左边的孩子，否则左边的孩子是2i。
3. 如果2i+1>n所以节点没有右孩子，否则右孩子是2i+1
验证：
第一条：
当i=1时，是根节点。当i>例如，结点为7，他的父母是7/2= 3；结点9双亲为4.
第二条：
结点6,62 = 12>因此，结点6不左的孩子是叶子结点。结点5，52 = 10.左孩子10，结点4，8.
第三条：
结点5，2*5+1>没有右孩子，结点4，就有右孩子。
更多Python相关知识，请移动Python视频教程继续学习！！