数据结构（八）之二叉树

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

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

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

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

·空二叉树

·只有一个根结点

·根结点只有左子树

·根结点只有右子树

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

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

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

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

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

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

其中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 结语
    以上是所有内容，希望对大家有所帮助。