二叉树的三种遍历
1、二叉树的定义
二叉树是n(n≥0)个节点的有限集合，它或者是空树(n=0),或者是有一个根节点及两颗不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树同样具有递归性质。
特别需要注意的是，尽管树和二叉树的概念之间有许多联系，但它们是两个不同的概念，树和二叉树之间最主要的区别是：二叉树结点的子树要区分左子树和右子树，即使在节点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。另外，二叉树结点最大度为2，二树中不限制节点的度数。
2、二叉树的性质
（1）二叉树第i层（i≥1）上至多有个节点
（2）高度为k的二叉树之多有个节点（k≥1）
（3）对于任一颗二叉树，若其终端的节点数为,度为2的节点数为
，则
（4）具有n个节点的完全二叉树的深度为
3、二叉树的存储结构
1）二叉树的顺序存储结构
用一组地址连续的存储单元存储二叉树中的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
2）二叉树的链式存储结构
由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。
4、二叉树的遍历
遍历二叉树的方法分别有先序遍历、中序遍历、后序遍历。
先序遍历：先遍历根节点，然后是左子树，最后是右子树；根节点->左子树->右子树
中序遍历：先遍历左子树，然后是根节点、最后是右子树；左子树->根节点->右子树
后序遍历：先遍历左子树，然后是右子树，最后是根节点；左子树->右子树->根节点
A
B C
D E
F G
先序遍历：ABDFEGC
中序遍历：DFBGEAC
后序遍历：FDGEBCA