数据结构（8）之二叉树
1 前言

今天我们来介绍一下二叉树，包括定义，数据结构定义，遍历，和二叉树的推倒。

转载请注明出处：http://blog.csdn.net/developer_zhang

2 详述2.1 二叉树定义

二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。

2.1.1 二叉树五种基本形态

空二叉树

只有一个根结点

根结点只有左子树

根结点只有右子树

根结点既有左子树又有右子树

2.1.2 特殊二叉树

斜树：所有的结点都只有左子树的二叉树叫做左斜树。 所有的结点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。

满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号i(1<i=<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可二叉树称为完全二叉树。

2.2 二叉树的存储结构2.2.1 顺序结构

该结构只适合与完全二叉树。将每个结点存放与数组之中。

2.2.2 二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

结构定义代码：

2.3 遍历二叉树
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序一次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法主要有：前序，中序，后续，层级四种方法。
2.3.1 前序遍历
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图，遍历的顺序为：ABDGHCEIF。
算法代码：
算法代码：
算法代码：
            由此得到后续遍历为：CBEFDA。
-例：二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，求前序序列。
解答：由后序BDCAFGE =》E为根结点。
            于是由中序ABCDEFG  =》分为两个树，左树ABCD，右树FG。A为E的左孩子。
            再由中序ABCDEFG，知道BCD为A的右子孙。再由后续BDCAFGE得知C为A的右孩子。
            由中序ABCDEFG，得知B是C的左孩子，D是C的右孩子。
            由后续BDCAFGE，得到G是E的右孩子，F就是G的孩子。根据中序ABCDEFG  =》F是G的左孩子。
            由此得出前序遍历：EACBDGF。

由此可知：
已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
也就是说已知中序遍历序列和另一种遍历序列，就能唯一确定一棵二叉树。
3 结语
    以上是所有内容，希望对大家有所帮助。