一、树的概念
树也是一种数据结构，大家可以想象一下，自然界中的树木，树木的叶子就相当于树的结点，那树其实就是n(n>0)个结点的有限集合。其中有一个特殊的结点叫做树根，这个结点没有前趋，除了根结点之外，其余的结点可以看成是m(m>=0)个互不相交的集合，每一个集合又可以看成是一棵树，也就是根的子树。也就是说，树其实就是由有限个子树组成，而且没有次序之分。如下图一所示。
图一
如上图所示，这个树组成了一个有限的集合t={a,b,c,d,e,f,g,h},其中a结点是根结点，它有两颗子树，t1 = {b,d,e,f}，以及t2 = {c,g,h},这两个子集互不相交。而t1该子树的根结点是b，它又有子集{d},{e},{f},同理可论证t2.
二、二叉树的概念
首先要注意一个知识点就是二叉树并不是树的特殊情形，他们是两种不同的数据结构。其次，二叉树可以为空，也可以只有左子树，或者右子树，亦或者由一个根结点加上左右两个互不相交的二叉树构成。
下面我们用python实现二叉树，来看看二叉树的实现原则：
1、第一个建立的元素是根结点
接下来我们再来看看二叉树的几种遍历方法：
树的遍历分为深度优先遍历和广度优先遍历，前者有前序、中序、后序，后者有层次遍历。一般来说，深度优先用递归，广度优先用队列。
图2
1、前序遍历
前序遍历是先遍历根结点，再遍历左子树，最后才遍历右子树。根据前序遍历，访问顺序为a->b->d-g,c->e>h,f->i
2、中序遍历
中序遍历是先遍历左子树，再遍历根结点，最后才遍历右子树。访问顺序为g->d->b->a,h->e->c,f->i
3、后序遍历
后续遍历是先遍历左子树，再遍历右子树，最后才遍历根结点。访问顺序是g->d->b->h->e-i->f->c->a
4、层次遍历
层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问，访问顺序是a->b->c->d->e->f->g->h->i
下面是实现前3种遍历的python代码，使用遍历
而对于层次遍历需要使用队列，可按如下步骤进行：
（1）初始化一个队列
（2）二叉树的根结点放入队列
（3）重复步骤(4)-(7)直至队列为空
（4）从队列中取出一个结点x
（5）访问结点x
（6）如果x存在左子结点，将左子结点放入队列
（7）如果x 存在右子结点，将右子结点放入队列
下面是代码实现：