数据结构中的二叉树是一种非常重要的非线性结构。

对于二叉树，最重要的算法就是二叉树的遍历，根据访问节点的顺序，分为三种

遍历方法：

前序遍历：（NLR）先访问根节点，然后访问左节点，{zh1}访问右节点

中序遍历：（LNR）先访问左节点，然后访问根节点，{zh1}访问右节点

后序遍历：（LNR）先访问左节点，然后访问右节点，{zh1}访问根节点

很清晰的可以看出，其实它就是根据根节点的访问次序区分的。

下面这个图就可以清晰的看出这三种遍历方法的区分：

存储结构

主要分两种：线性存储结构和链式存储结构。

线性存储：就是存储在数组中，这时候有一个很重要的问题：二叉树的节点以什么顺序存储在数组中？这种顺序必须体现出二叉树的父子关系。

解决办法就是：

1.    把每棵树都看作是一个满二叉树（满二叉树就是除了叶子节点每个节点都有左右子节点），如果这棵树是非满二叉树，就主动给它补全，而补上的节点都是NULL；

2.    按层遍历；

为了说明问题，以上面的那棵xx二叉树为例说明：

它的存储结构结构是

A B C D E F G NULL NULL NULL NULL H NULL NULL NULL

说明：

前三层是完整的，按层顺序访问就是A B C D E F G

第四层中，应该是找出D E F G的8个子节点，D E没有。OK，就补了4个NULL值，F只有左节点，所以它的两个子节点为H NULL,G没有子节点，那就是两个NULL NULL

这下，就可以通过解析数组，清晰的把各个节点的父子结构拿出来了。

链式存储：

这个估计基本不用解释，大家都知道咋存储了，因为很简单，它就是用一个二叉链表存储的：

这个大家都很容易理解，我们只要知道了这棵树的根节点，就可以访问到它所以的节点值了。

二叉树存储结构分析：

我们知道，数组的优点是可以随机访问，因为它有下标，但是插入和删除比较麻烦，尤其是从{dy}位就删除或插入，需要移动整个数组；而链表正好相反，插入和删除非常方便，这要修改它的左右值就可以，但是随机访问不方便，因为它需要顺序的遍历；

二叉树的存在意义

二叉树具有两种数据结构的优点：一种是有序数组，一种是链表；在树中查找数据项的速度和有序数组一样快，在树中添加和删除数据和链表一样快。