在了解二叉树之前，我们先来看一下

树的定义

树， 木本植物之总名，主要由根、干、枝、叶、花、果组成。。。。
皮一下很开心
进入正题了
1，树是有n（n>=0）个结点组成的有限集合T，n=0时称为空树，若n>1时，其余结点被分为m(m>0)个互不相交的子集T1,T2…Tm，其中每个子集本身又是一棵树，称其为根的子树（Subtree）。
这是树的递归定义，即用树来定义树，只有一个结点的树必定由根组成。

树的基本术语

1，结点：一个数据元素，及其若干指向其子树的分支，如上图中的圆圈中的E就是一个结点
2，结点的度：结点所拥有的子树的棵树称为结点的度。
3，树的度：树中结点度的最大值称为树的度。
4，叶子结点：树中度为 0 的结点称为叶子结点(或终端结点)。
5，非叶子结点：度不为 0 的结点称为 非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。
6，孩子结点：**一个结点的子树的根（非叶子结点）**称为该结点的孩子结点(child)或子结点,给个例子，上图中，E是B的孩子结点
7，双亲结点：同样的，B是E的双亲结点，也称为父节点
8，兄弟结点：同一父亲的孩子结点互为兄弟结点，如B和C
9，森林(forest)：是 m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点 删除，剩余的子树就构成了森林。

二叉树(Binary tree)

二叉树是 n(n≥0)个结点的有限集合。若 n=0 时称为空树，否则： 有且只有一个特殊的称为树的根(Root)结点；
若 n>1 时，其余的结点被分成为二个互不相交的子集 T1,T2，分别称之为左、右 子树，并且左、右子树又都是二叉树。
由此可知，二叉树的定义是递归的。
二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树 的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关 树的术语也都适用于二叉树。

二叉树的基本形态

二叉树的本质（重点）

性质1：在非空二叉树中，第 i 层上至多有 2^(i − 1) 个结点（i>=1）
性质2：深度为 k 的二叉树至多有 2^k-1 个结点（k>=1）
性质3：对任何一棵二叉树，若其叶子结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

满二叉树

一棵深度为 k 且有 2^k-1 个结点的二叉树称为满二叉树(Full Binary Tree)。
满二叉树的特点：
1，每一层上的结点数总是最大结点数
2，所有的支结点都有左、右子树
3、可对满二叉树的结点进行连续编号，若规定从根节点开始，按自上而下，自左而右的原则进行

完全二叉树

一颗深度为 k ，且在k-1层以及之前所有层的结点都是满的，仅在最后一层的叶子结点从右至左有所缺少，都可以视为完全二叉树，注意，一定是从右至左有所缺少，否则都不能视为完全二叉树，如图

二叉树的储存结构

1，顺序存储结构
用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素对于完全二叉树上编号为 i 的结点元素存储在一维数组的下标值为 i-1 的分量中 对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中。

2，链式存储结构
设计不同的结点结构可构成不同的链式存储结构。
**二叉链表结点：**有三个域，一个数据域，两个分别指向左右子结点的指针域
**三叉链表结点：**除二叉链表的三个域外，再增加一个指针域，用来指向结点的父 结点

有一棵一般的二叉树，以二叉链表和三叉链表方式存储的结构图：

遍历二叉树及其应用

遍历二叉树(Traversing Binary Tree)是指按指定的规律对二叉树中的每个结点访问 一次且仅访问一次。
所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。
二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找 一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。

二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍 历了二叉树。
若以 L、D、R 分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方 案：DLR、LDR、LRD、DRL、RDL、RLD。
若规定先左后右，则只有前三种情况三 种情况，分别是：
DLR——先(根)序遍历。
LDR——中(根)序遍历。
LRD——后(根)序遍历。

查找算法

1，顺序查找
从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到
两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。
平均要与表中一半以上元素进行比较，最坏情况下需要比较 n 次。
如果线性表为无序表，则不管是“ 顺序存储结构 ” 还是“ 链式存储结构”，都只能用顺序
查找。
即使是有序线性表，如果采用 “链式存储结构”，也只能用顺序查找。

2，二分法查找
二分查找又称折半查找，它是一种效率较高的查找方法。
【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相
等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位
置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一
子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在
为止，此时查找不成功。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点
是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变
动而查找频繁的有序列表。

代码实现：

def binary_chop(alist, data):
	n = len(alist)  #计算列表长度
	if n < 1:  #如果小于1，则代表列表中没有data这个数据
		return False
	mid = n // 2  #二分列表长度
	 if alist[mid] > data:  #取mid对应的值与data作比较
		return binary_chop(alist[0:mid], data)  #如果大于则在有分区进行递归
	elif alist[mid] < data:  
		return binary_chop(alist[mid+1:], data)  #否则在左分区进行递归
	else:
		return True  #如果相等，则代表找到了这个值，返回True

后面还有很多排序算法的知识，可以看看我的这篇博客
五大算法
快排算法
python内置Timsort算法

下面可以给大家留两道经典的题目：
题目1：一个完全二叉树有七百个结点，问该二叉树有多少个叶子结点
题目2：一颗二叉树的叶子节点有5个，出度为1的结点有3个，该二叉树的结点总个数是？
不会的就在低下评论，我会给出解答，当然会的也可以留下你的答案